Python: Recursive Fibonacci

Before going to the recursive solution, let’s check the iterative one given below:

def fibo(n):
 
	prev = 0
	current = 1
	result = 0
 
	while result <= n:
 
		result = prev+current
		prev = current
		current = result
 
	return result
 
print(fibo(5))

Here’s a hand drawn explanation of how the Fibonacci numbers are calculated:

This makes us store the last two values as prev and current to calculate the current result. After which we will move prev and current or update them to calculate the next result.

Now here’s the recursive solution:

def fibo(n):
 
	if n==0 or n==1:
		return n
 
	return fibo(n-1) + fibo(n-2)
 
print(fibo(7))

It will print the 7th Fibonacci number as follows:

The problem with recursive solution is that it gets huge and repeats itself as follows:

The time spent on calls in the highlighted area can be saved by storing the results and then returning the stored results instead of calculating them again. This is called Memoization.

Here’s memoized recursive solution for Fibonacci:

class Fibrec:
 
	def __init__(self):
		self.memo = {} #creates dict 
 
	def fibo(self, n):
 
		if n < 0: raise ValueError("incorrect value")
 
		elif n in [0,1]: 
			return n
 
		if n in self.memo:
			return self.memo[n]
 
		result = self.fibo(n-1) + self.fibo(n-2)
 
		self.memo[n] = result # store result in dict
 
		return result
 
f = Fibrec()
print(f.fibo(8)) # prints 21

That’s all in this post 🙂