Fibonacci Series in Python using Recursion

Fibonacci Series in Python using Recursion

In this tutorial, we present you two ways to compute Fibonacci series using Recursion in Python.

The first way is kind of brute force. The second way tries to reduce the function calls in the recursion.

The advantage of recursion is that the program becomes expressive.

Fibonacci series using Recursion

In the following program, we write a function fibonacci() that computes nth element of a Fibonacci series using recursion.

def fibonacci(n):
	if n<=1:
		return n
	else:
		return(fibonacci(n-1) + fibonacci(n-2))

n = int(input('Enter a number, N, N>=2 : '))

fibo_series = []

for i in range(0,n):
	fibo_series.append(fibonacci(i))
	
print(fibo_series)

Output

D:\>python example.py
Enter a number, N, N>=2 : 10
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

D:\>python example.py
Enter a number, N, N>=2 : 5
[0, 1, 1, 2, 3]

About the Performance

If you consider performance, this is a blunder. Why? Here is the reason. Lets keep aside the discussion of creating stack for each function call within the function. When you are calculating nth Fibonacci element, all the Fibonacci elements prior to nth element has to be calculated again, irrespective of the fact that we already calculated them.

Improvised Program

In this example, we consider the fact that previous 0, 1, 2, . ., i-1th elements are already calculated when you are generating ith element.

fibo_series = [0, 1]

def fibonacci(n):
	if n<=len(fibo_series) and n>0:
		return fibo_series[n-1]
	else:
		fn = fibonacci(n-1) + fibonacci(n-2)
		if n>len(fibo_series):
			fibo_series.append(fn)
		return fn

n = int(input('Enter a number, N, N>=2 : '))

fibonacci(n)

print(fibo_series)

Output

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

Summary

In this tutorial of Python Examples, we learned how to generate Fibonacci Series in Python using Recursion technique.