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.
Example 1: Generate Fibonacci Series using Recursion in Python
In this example, we write a function 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)
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.
Example 2: Generate Fibonacci Series using Recursion in Python [Improvised]
In this example, we consider the fact that previous
0, 1, 2, . ., i-1th elements are already calculated when you are generating
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)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
In this tutorial of Python Examples, we learned how to generate Fibonacci Series in Python using Recursion technique.