## DEV Community kkumar-gcc

Posted on • Updated on • Originally published at Medium

# Program for Fibonacci Numbers

### What is the Fibonacci series?

The Fibonacci sequence is a sequence where the next term is the sum of the previous two terms. The first two terms of the Fibonacci sequence are 0 followed by 1.

``````The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21 ....
``````

In mathematical terms,the sequence Fn of Fibonacci numbers is defined by recursion relation

``````Fn = Fn-1 + Fn-2
``````

where

``````F0 = 0 , F1 = 1
``````

### We will discuss three ways to write the Fibonacci series program :

• Fibonacci series using recursion
• Fibonacci series using Iterative method
• Fibonacci series using Matrix Exponentiation

### (1) Recursive Method :

A simple method that is a direct recursive implementation mathematical recurrence relation is given above.

``````//pseudo code
RFib(n)
{
if n=0 return 0;
else if n=1 return 1;
else return (RFib(n-1)+RFib(n-2));
}
``````

Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential.
Extra Space: O(n) if we consider the function call stack size, otherwise O(1).

Run Replit

### (2) Iterative Method :

We can optimize the space used in Recursive Method by storing the previous two numbers only because that is all we need to get the next Fibonacci number in series.

``````//pseudo code
IFib(n)
if n=0 return 0;
else if n=1 return 1;
else {   a <= 0; b<=1;
for(i=2 to n) do
{ temp <= b;
b<= a+b;
a <= temp;
}
return b;
``````

Time complexity: O(n)
Extra space: O(1)

Run Replit

### (3) Matrix Exponentiation :

Let n > 1  Time complexity : O(log(n))
Extra space : O(log(n)) if we consider the function call stack size, otherwise O(1).

Run Replit