Can you write a recursive function to compute the Fibonacci sequence?

One of the common examples of recursion in programming is computing the Fibonacci sequence. In Python, it can be realized like below:

def fibonacci(n):
    if n <= 0:
        return "Input should be a positive integer"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

The above function calculates the Fibonacci sequence utilising the nature of the Fibonacci sequence, where each number in the sequence is the sum of the two preceding ones (considering that F(0) = 0, and F(1) = 1). Hence, the term ‘fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)‘.

Now, the recursive call happens with ‘fibonacci(n-1)‘ and ‘fibonacci(n-2)‘, but what are they? They are essentially tasks that are a version of the original computation ‘fibonacci(n)‘ but on simpler inputs. Here, values decrease with ‘n-1‘ and ‘n-2‘. The function will keep calling itself, decreasing the input on each call, until it reaches a base case.

Recursion always needs a base case — the situation where the function does not call itself — to avoid infinite recursion. In this case, it’s when ‘n == 1‘ or ‘n == 2‘.

It is important to note that this solution while it is simple and direct, it is not efficient for large inputs of ‘n‘ as it does redundant computations due to the overlapping subproblems in the recursion tree. This overlapping can lead us to compute the same Fibonacci number multiple times. This problem can be avoided by using techniques such as Dynamic Programming.

For instance, an illustration with ‘fibonacci(5)‘, the recursion tree is as follows:

                    fibonacci(5)
                   /            \
             fibonacci(4)          fibonacci(3)
             /      \              /      \
      fibonacci(3)  fibonacci(2) fibonacci(2) fibonacci(1)
      /     \        return 1     return 1    return 0
 fibonacci(2) fibonacci(1)
 return 1     return 0

As can be seen from the recursion tree, ‘fibonacci(3)‘ and ‘fibonacci(2)‘ are being calculated numerous times. With bigger values of ‘n‘, the same computation increases exponentially, leading to inefficiency. This can be avoided with memoization or other Dynamic Programming techniques.