In this article, we will implement different algorithms to calculate n^th Fibonacci number.

Table of contents:

• Introduction to Fibonacci numbers
• Using loops
• Using recursion
• Using memoization
• Using a mathematical approach

Introduction to Fibonacci numbers

In the field of mathematics, the Fibonacci numbers(denoted as F_n) is a sequence, in which each number is the sum of the two preceding numbers.
The sequence is known as the Fibonacci sequence. It commonly starts from 0 and 1, although we can start from 1 and 1 or from 1 and 2. Starting from 0 and 1, the next few values in the sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

The recursive formula of a Fibonacci sequence is given as:-

F_n = F_n-1 + F_n-2

In this article at OpenGenus, we will use different methods to implement an algorithm to calculate the n^th number in the above Fibonacci sequence starting from 0, 1.

Using loops

We can use loops to find the n^th Fibonacci number by initializing the first two numbers as variables and looping from 3 to n where each term is the sum of previous 2 terms.

Implementing the algorithm

We will define a function which takes an integer value n. Inside the body, we initialise two variables a=0 and b=1, then we will check for the case of n=1 or n=2, if n=1 then return a and if n=2 then return b. If n is neither 1 or 2, then using for loop ranging from 3 to n inclusive, we will calculate the next fibonacci number and store it and increment a and b to the next values in the fibonacci sequence. When the loop will end, the second variable b will be storing or pointing to the value of n^th, now we just return b.

Python code of a function to calculate the n^th Fibonacci number using loops

def Fib(n):
    a = 0
    b = 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(3,n+1):
            c = a + b
            a = b
            b = c
        return b
    
n = 5
print(Fib(n))

Output:
3

In the above algorithm, the function Fib takes an integer value n as an argument. If n is 1, it returns the first number a which is initialized by 0, if n is 2, it returns the second number b which is 1, otherwise it iterates through 3 to n inclusive and calculates the next term by adding a and b making a and b the previous 2 terms of i^th iteration. The algorithm loops through every number from 1 to n inclusive, so, the time complexity of this algorithm is O(n). Since, the algorithm uses the constant space, the space complexity of the algorithm is O(1).

Using recursion

We can use recursion to find the n^th Fibonacci number by using the recursive formula for Fibonacci sequence, F_n = F_n-1 + F_n-2.

Implementing the algorithm
We will define a function which takes an integer value n. Inside the body, we will check for the base case of n=1 or n=2, if n=1 then return 0 and if n=2 then return 1. If n is neither 1 or 2, then using the recursive approach, we will return the sum of previous two terms by calling the function two times one with an argument n-1 and other with n-2.

Python code of a function to calculate the n^th Fibonacci number using recursion

def Fib(n):
    if n == 1 :
        return 0
    if n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

n = 6
print(Fib(n))

Output:
5

In the above algorithm, the function Fib takes an integer value n as an argument, returns 0 if n is 1, returns 1 if n is 2, otherwise returns the recursive clause Fib(n-1) + F(n-2). This function recursively calculates every term until a base case is hit which is n=1, and n=2. Hence, this also has a linear time complexity, O(n). This algorithm at every step runs the function twice for previous two values.

Hence, the time complexity of this function is O(2ⁿ). This algorithm has a space complexity of O(n) if we consider the function call stack size, otherwise it has a space complexity of O(1).

Using memoization

This method is simillar to recursive method but stores the value at each recursive step in order to minimize the calculation of function with same arguments again and again.

Implementing the algorithm

We will define a function which takes an integer value n and a default argument memoize to store the base conditions. Inside the body, we will check that whether n is in memoize or not, if memoize contains n, then will return the value of key n, otherwise calculate the value for n^th key using recursive approach and returning the n^th key value from memoize.

Python code of a function to calculate the n^th Fibonacci number using memoization technique of dynamic programming

def Fib(n, memoize={1: 0, 2: 1}):
    if n in memoize:
		return memoize[n]
	else:
		memoize[n] = Fib(n-1, memoize) + Fib(n-2, memoize)
		return memoize[n]

n = 5
print(Fib(n))

Output:
3

In the above algorithm, the function Fib takes an integer n as an argument, and a default argument of type dictionary named memoize containing the base cases. Inside the body of the function, we check whether the integer n is in memoize, if yes, the returns the value mapped to key n in memoize, otherwise, calculate the value using the recursive formula and store the value mapping to the key n in dictionary for later use in the recursive steps and return the value calculated.

This algorithm reduces many steps and runs in a linear time complexity, O(n), much better compared to the recursive method. Since, this algorithm stores all the Fibonacci numbers less than equal to n, it has a space complexity of O(n).

Using a mathematical approach

We can use a mathematical approach to find the n^th Fibonacci number by using the concept of second order linear homogeneous recurrence relation with constant coefficients. Here we will use Binet's Fibonacci number formula.

Deriving the Binet's formula

The characteristic polynomial for the Fibonacci's recurrence F_n = F_n-1 + F_n-2 is,

x² = x + 1

The solutions of the characteristic equation are,

ϕ = (1+√5)/2
ψ = (1-√5)/2

so the closed formula for the Fibonacci sequence must be of the form,

f_n = uϕⁿ + vψⁿ

for some real numbers u, v.
Now we use the boundary conditions of the recurrence, that is, f₀ = 0 and f₁ = 1, which means we have to solve the system

0 = uϕ⁰ + vψ⁰
1 = uϕ¹ + vψ¹

The first equation simplifies to u = -v, and substituting into the second one gives:

1 = u ((1+√5)/2) - u ((1-√5)/2)
u = 1/√5
v = -1/√5

Hence, the formula for n^th Fibonacci formula is,

F_n = ( ϕ^n-1 - ψ^n-1 ) / √5

Implementing the algorithm

We will define a function which takes an integer value n. Inside the body, we will store the constants (1+√5)/2 and (1-√5)/2 to use in our formula expression. Then the function will return the floor of Binet's formula. Here we are taking floor to get the desired result, since, the Binet's formula returns the approximate value.

Python code of a function to calculate the n^th Fibonacci number using a mathematical approach

def Fib(n):
	phi1 = (1 - 5 ** 0.5) / 2
	phi2 = (1 + 5 ** 0.5) / 2
	return (phi2**(n-1) - phi1**(n-1)) // (5**0.5)

n = 5
print(Fib(n))

Output:
3

In this algorithm, we take the solutions of the characteristic equation of the recurrence relation F_n = F_n-1 + F_n-2 as phi1, and phi2. We then determine the general formula for the n^th Fibonacci number which is taking the floor value of ratio of the difference between the (n-1)^th powers of phi1 and phi2, and square root of 5.

The formula is given as:-

Floor ( ( phi2^n-1 - phi1^n-1 ) / ( 5^0.5 ) )
Note that here we used integer division, Pythonic notation which is simillar to calculating the floor of the value obtained after division.

This algorithm takes O( log(n) ) time as the exponentiation step take log(n) time. Since, this algorithm stores only two constants phi1, and phi2, thus has a space complexity of O(1).

With this article at OpenGenus, you must have the complete idea of Different ways to calculate nᵗʰ Fibonacci number.