# Python Program - Fibonacci Sequence

Fibonacci terms are generally represented as *F _{n}*. A Fibonacci term is the sum of two previous terms and starts with

*0*and

*1*. Mathematically, it can be represented as:

*F _{n} = F_{n-1} + F_{n-2}*

With boundary conditions: *F _{0}* = 0 and

*F*= 1

_{1}The Fibonacci Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

### Method 1: Using Recursive method

In the example below, a recursive function called *fib()* is created to find out the nth term of Fibonacci sequence.

def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) print("Fibonacci 5th term:", fib(5)) print("Fibonacci 6th term:", fib(6)) print("Fibonacci 7th term:", fib(7))

The above code will give the following output:

Fibonacci 5th term: 5 Fibonacci 6th term: 8 Fibonacci 7th term: 13

### Method 2: Using Dynamic Programming

The Fibonacci term can also be estimated using dynamic programming. As compared to the recursive method, it calculates a specific term of the sequence only once.

def fib(n): #creating a list which contains Fibonacci terms f = [0 for i in range(0,n+1)] f[0] = 0 f[1] = 1 for i in range(2, n+1): f[i] = f[i-1] + f[i-2] return f[n] print("Fibonacci 6th term:", fib(6)) print("Fibonacci 7th term:", fib(7)) print("Fibonacci 8th term:", fib(8))

The above code will give the following output:

Fibonacci 6th term: 8 Fibonacci 7th term: 13 Fibonacci 8th term: 21

### Method 3: Using Short-hand If-else method (Ternary operator)

This can also be achieved using short-hand if-else statements.

def fib(n): y = 0 if (n == 0) else 1 if (n == 1) else fib(n-1) + fib(n-2) return y print("Fibonacci 8th term:", fib(8)) print("Fibonacci 9th term:", fib(9)) print("Fibonacci 10th term:", fib(10))

The above code will give the following output:

Fibonacci 8th term: 21 Fibonacci 9th term: 34 Fibonacci 10th term: 55

### Method 4: Space optimized method

In this method, only three variables are used which changes in each iteration and finally nth term of Fibonacci Sequence is calculated.

def fib(n): a, b = 0, 1 c = 0 if n == 0: return a for i in range(2, n+1): c = a + b a = b b = c return b print("Fibonacci 9th term:", fib(9)) print("Fibonacci 10th term:", fib(10)) print("Fibonacci 11th term:", fib(11))

The above code will give the following output:

Fibonacci 9th term: 34 Fibonacci 10th term: 55 Fibonacci 11th term: 89

### Method 5: Using power of matrix

A Fibonacci sequence term can also be calculated as power of matrix. A Fibonacci sequence holds below mentioned property:

To calculate *F _{n}*,is calculated and

*A*will be the

_{01}*F*.

_{n}def fib(n): initial = [[1, 1], [1, 0]] Final = [[1, 1], [1, 0]] if n == 0: return 0 else: for i in range(1, n): a = Final[0][0]*initial[0][0] + Final[0][1]*initial[1][0] b = Final[1][0]*initial[0][0] + Final[1][1]*initial[1][0] c = Final[0][0]*initial[0][1] + Final[0][1]*initial[1][1] d = Final[1][0]*initial[0][1] + Final[1][1]*initial[1][1] Final[0][0] = a Final[1][0] = b Final[0][1] = c Final[1][1] = d return Final[0][1] print("Fibonacci 10th term:", fib(10)) print("Fibonacci 11th term:", fib(11)) print("Fibonacci 12th term:", fib(12))

The above code will give the following output:

Fibonacci 10th term: 55 Fibonacci 11th term: 89 Fibonacci 12th term: 144

### Recommended Pages

- Python Program - To Check Prime Number
- Python Program - Bubble Sort
- Python Program - Selection Sort
- Python Program - Maximum Subarray Sum
- Python Program - Reverse digits of a given Integer
- Python Program - Merge Sort
- Python Program - Shell Sort
- Stack in Python
- Queue in Python
- Python Program - Find LCM of Two Numbers
- Python Program - To Check Whether a Number is Palindrome or Not
- Python Program - To Check Whether a String is Palindrome or Not
- Python Program - Heap Sort
- Python Program - Quick Sort
- Python - Swap Two Numbers without using Temporary Variable
- Python Program - To Check Armstrong Number
- Python Program - Counting Sort
- Python Program - Radix Sort
- Python Program - Find Largest Number among Three Numbers
- Python Program - Print Floyd's Triangle