Recursion Algorithm

Let’s start with a basic example to get an idea of how a recursive function works:

def recursive(input):
  if input <= 0:
    return input
  else:
    output = recursive(input -1 )
    return output

Below is the demonstration with the input=2.

Implementation of the Fibonacci Sequence

Now, we are going to take a look at recursion with a famous example: the Fibonacci Sequence. The Fibonacci Sequence follows one rule: get the next number in the sequence by adding the two previous numbers. Here is an example of the sequence:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...]

We start with (val_0 = 0) –> (val_1 = 0 + 1 = 1).

Then, we step through each value: (val_2 = val_0 + val_1 = 0 + 1 = 1) –> *(val_3 = val_1 + val_2 = 1 + 1 = 2), …etc

We implemente get_fib() in a recursive way:

def fb(position):
    if position > 1:
        output = fb(position-2) + fb(position-1)
        return output
    
    else:
        if position == 1:
            output = 1
            return output
        elif position == 0:
            output= 0
            return output

Actually, we can realize that for position 0 and 1, the output is actuaclly the position so:

 def fb(position):
    if position > 1:
        output = fb(position-2) + fb(position-1)
        return output
    
    else:
        if position == 1 or position == 0:
        output = position
        return position

        Here is the compact version:

 def fb(position):
 	if position == 1 or position == 0:
        output = position
        return position
    else:
        return fb(position-2) + fb(position-1)

Tips:

You may have noticed that this solution will compute the values of some inputs more than once. For example get_fib(4) calls get_fib(3) and get_fib(2), get_fib(3) calls get_fib(2) and get_fib(1) etc… The number of recursive calls grows exponentially with n.

In practice if we were to use recursion to solve this problem we should use a hash table to store and fetch previously calculated results. This will increase the space needed but will drastically improve the runtime efficiency.