Recursion: a function that calls itself
1
2
3
4
5
6
7
def recursive(input):
#base case: exit condition
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:
1
2
3
4
5
6
7
8
9
10
11
12
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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.