# 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.

### Example 1: Generate Fibonacci Series using Recursion in Python

In this example, we write a function 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]``````

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.

### Example 2: Generate Fibonacci Series using Recursion in Python [Improvised]

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.