## 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.