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 n
th element of a Fibonacci series using recursion.
Python Program
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 n
th Fibonacci element, all the Fibonacci elements prior to n
th 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-1
th elements are already calculated when you are generating i
th element.
Python Program
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.