Python Program - Fibonacci Sequence


Advertisements

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

Example: Using Recursive method

In the below example, 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))

Output

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

Example: 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))

Output

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

Example: 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))

Output

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

Example: 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))

Output

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

Example: Using power of matrix

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

$$\begin{pmatrix}1 & 1\\\ 1 & 0\end{pmatrix}^n$$ = $$\begin{pmatrix}F_{n+1} & F_n\\\ F_n & F_{n-1}\end{pmatrix}$$

To calculate $$F_n$$, $$A = \begin{pmatrix}1 & 1\\\ 1 & 0\end{pmatrix}^n$$ is calculated and $$A_{01}$$ will be the $$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))

Output

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




Advertisements