TechVidvan

Fibonacci Series – Algorithm and Implementation

Fibonacci series is a special kind of series in which the next term is equal to the sum of the previous two terms. Thus, the initial two numbers of the series are always given to us.

For example, let F0 and F1 denote the first two terms of the Fibonacci series. Then, let F0 = 0 and F1 = 1.
Suppose we wish to calculate 10 terms of this Fibonacci series. Then, the series will be:
F10 = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Methods to find Fibonacci Series:

There are various algorithms or methods by which we can find the Fibonacci series for a given set of terms. The most common methods are:

1. Using recursion

2. Without using recursion or using Dynamic programming

3. Space optimized method in DP

Let us see their implementations one by one.

Algorithm for Iterative Fibonacci Series:

The iterative approach is the dynamic programming approach. It makes use of a loop to perform the addition of the previous two terms. The algorithm for the iterative approach will be:

Procedure Iterative_Fibonacci(n):
    int f0, f1, fib
    f0 = 0
    f1 = 1
    display f0, f1
    for int i := 1 to n:
        fib := f0 + f1   
        f0 := f1
        f1 := fib
        display fib
    END for loop
END Iterative_Fibonacci

Algorithm for Recursive Fibonacci Series:

We can also use recursion to generate the Fibonacci series. The pseudo-code for the recursive method is:

Procedure Recursive_Fibonacci(n)
    int f0, f1
    f0 := 0
    f1 := 1
    if(n <= 1):
        return n
    return Recursive_Fibonacci(n-1) + Recursive_Fibonacci(n-2)
END Recursive_Fibonacci

Implementation Using DP(Iterative Approach):

Implementation of Fibonacci Series in C:

int Iterative_fib(int n)
{
    int fib[n+2]; 
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
      fib[i] = fib[i-1] + fib[i-2];
    return fib[n];
}

int main ()
{
    int n = 9;
    printf("%d", Iterative_fib(n));
    return 0;
}

Fibonacci series Implementation in C++:

#include<bits/stdc++.h>

int Iterative_fib(int n)
{
    int fib[n+2]; 
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
      fib[i] = fib[i-1] + fib[i-2];
    return fib[n];
}

int main ()
{
    int n = 9;
    cout<< Iterative_fib(n);
    return 0;
}

Implementation of Fibonacci Series in Java:

class Fibonacci
{
    static int Iterative_fib(int n)
  {
      int fib[] = new int[n+2]; 
      fib[0] = 0;
      fib[1] = 1;
  
      for (int i = 2; i <= n; i++)
        fib[i] = fib[i-1] + fib[i-2];
      return fib[n];
  }
  
  public static void main (String args[])
  {
    int n = 10;
    System.out.println(Iterative_fib(n));
  }
}

Fibonacci series Implementation in Python:

def Iterative_fib(n):
  fib = [0, 1]
  for i in range(2, n+1):
    f.append(fib[i-1] + fib[i-2])
  return fib[n]
  
print(Iterative_fib(10))

Implementation Using Space Optimization in DP:

Implementation of Fibonacci series in C:

#include<stdio.h>
int SO_fib(int n)
{
    int num1 = 0, num2 = 1, num3;
    if( n == 0)
      return num1;
    for (int i = 2; i <= n; i++)
    {
      num3 = num1 + num2;
      num1 = num2;
      num2 = num3;
    }
    return num2;
}

int main ()
{
    int n = 10;
    printf("%d", SO_fib(n));
    return 0;
}

Fibonacci series Implementation in C++:

#include<bits/stdc++.h>
int SO_fib(int n)
{
    int num1 = 0, num2 = 1, num3;
    if( n == 0)
      return num1;
    for (int i = 2; i <= n; i++)
    {
      num3 = num1 + num2;
      num1 = num2;
      num2 = num3;
    }
    return num2;
}

int main ()
{
    int n = 10;
    cout << SO_fib(n));
    return 0;
}

Implementation of Fibonacci series in Java:

class Fibonacci
{
  static int SO_fib(int n)
  {
    int num1 = 0, num2 = 1, num3;
    if (n == 0)
      return num1;
    for (int i = 2; i <= n; i++)
    {
      num3 = num1 + num2;
      num1 = num2;
      num2 = num3;
    }
    return num2;
  }

  public static void main (String args[])
  {
    int n = 10;
    System.out.println(SO_fib(n));
  }
}

Fibonacci series Implementation in Python:

def SO_fib(n):
  num1 = 0
  num2 = 1
  if n < 0:
    print("Incorrect input")
  elif n == 0:
    return num1
  elif n == 1:
    return num2
  else:
    for i in range(2, n+1):
      num3 = num1 + num2
      num1 = num2
      num2 = num3
    return num2

print(SO_fib(10))

Implementation Using Recursion:

Implementation of Fibonacci series in C:

#include<stdio.h>
int Recursive_fib(int n)
{
    if (n <= 1)
      return n;
    return Recursive_fib(n-1) + Recursive_fib(n-2);
}

int main ()
{
    int n = 10;
    printf("%d", Recursive_fib(n));
    return 0;
}

Fibonacci series Implementation in C++:

#include<bits/stdc++.h>
int Recursive_fib(int n)
{
    if (n <= 1)
      return n;
    return Recursive_fib(n-1) + Recursive_fib(n-2);
}

int main ()
{
    int n = 10;
    cout << Recursive_fib(n);
    return 0;
}

Implementation of Fibonacci Series in Java:

class Fibonacci
{
  static int Recursive_fib(int n)
  {
      if (n <= 1)
      return n;
      return Recursive_fib(n-1) + Recursive_fib(n-2);
  }
  
  public static void main (String args[])
  {
      int n = 9;
      System.out.println(Recursive_fib(n));
  }
}

Fibonacci series Implementation in Python:

def Recursive_fib(n):
  if n<0:
    print("Incorrect input")
  elif n==0:
    return 0
  elif n==1:
    return 1
  else:
    return Recursive_fib(n-1) + Recursive_fib(n-2)

print(Recursive_fib(10))

Complexity Analysis of Fibonacci series:

Different methods generate different complexities for the same problem. These complexities are:

Method Time complexity Space complexity
Using recursion T(n) = T(n-1) + T(n-2) O(n)
Using DP O(n) O(1)
Space optimization of DP O(n) O(1)
Using the power of matrix method O(n) O(1)
Optimized matrix method O(log n) O(log n)
Recursive method in O(log n) time O(log n) O(n)
Using direct formula O(log n) O(1)
DP using memoization O(n) O(1)

Conclusion:

In this article, we have defined the Fibonacci series. We have also seen various methods with which we can implement it. We have implemented these methods in C, C++, Java and Python.