DEV Community

Cover image for Program for Fibonacci Numbers
kkumar-gcc
kkumar-gcc

Posted on • Edited on • Originally published at Medium

2 2 1 1 1

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 ....
Enter fullscreen mode Exit fullscreen mode

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

Fn = Fn-1 + Fn-2 
Enter fullscreen mode Exit fullscreen mode

where

F0 = 0 , F1 = 1
Enter fullscreen mode Exit fullscreen mode

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));
}
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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

Run Replit

(3) Matrix Exponentiation :

Let n > 1

Matrix Exponentiation

pseudo code

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

Run Replit

Thanks for reading

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs