Home » Interview » Algorithm » Fibonacci numbers

Fibonacci numbers


Fibonacci numbers are the numbers that form the series called Fibonacci series and are represented as Fn. The first two Fibonacci numbers are 0 and 1 respectively i.e. F0=0 and F1=1. Starting from the third Fibonacci number each Fibonacci number is the sum of its previous two numbers in the series.

Fn = Fn-1 + Fn-2

The fibonacci series – 0, 1, 1, 2, 3, 5, 8, 13……

Given an integer n. Find the nth Fibonacci number.

Example

Input: n=5

Output: 5

Input: n=9

Output: 34

Recursive Method

Algorithm

  1. Initialise a variable n.
  2. Base case – if n is less than equal to 1 return n.
  3. Recursive case – return fn (n-1) + fn (n-2).

Time Complexity : O(1.6180)n     (1.6180 is also known as the golden ratio)

Space Complexity : O(1)

C++ Program for Fibonacci numbers

#include<bits/stdc++.h> 
using namespace std; 
  
int fn(int n){ 
    if(n<=1) 
        return n; 
    return fn(n-1) + fn(n-2); 
} 
  
int main (){ 
    int n=6; 
    cout<<fn(n); 
    return 0; 
}
Output :
8

Java Program for Fibonacci numbers

class fibNumbers{ 
    static int fn(int n){ 
        if(n<=1) 
           return n; 
        return fn(n-1) + fn(n-2); 
    } 
       
    public static void main (String args[]){ 
        int n = 6; 
        System.out.println(fn(n)); 
    } 
}
Output : 
8

Recursive tree for the above code

Fibonacci numbers

We can see from the above tree that some functions are being called more than once. 

Dynamic Programming Method

Re-calculations of same functions like above can be avoided using DP.

Algorithm

  1. Initialize a variable n and an array f to store Fibonacci numbers.
  2. Initialize the first two elements of array as 0 and 1 respectively..
  3. Traverse all the values till n starting from 2 one by one and update the array values as the sum of the previous two elements in array.
  4. Return f[n].

Time Complexity: O(n)     

Space Complexity: O(n)

C++ Program for Fibonacci numbers

#include<bits/stdc++.h>
using namespace std;

int fn(int n){ 
  int f[n+2];
  
  f[0] = 0; 
  f[1] = 1; 
  
  for(int i=2; i<=n; i++){ 
      f[i] = f[i-1] + f[i-2]; 
  } 
  
  return f[n]; 
} 
  
int main (){ 
  int n = 6; 
  cout<<fn(n);
  return 0; 
}
Output : 
8

Java Program for Fibonacci numbers

class fibNumbers{ 
    static int fn(int n){ 
        int[] f = new int[n+2]; 
        
        f[0] = 0; 
        f[1] = 1; 
        
        for(int i=2; i<=n; i++){ 
            f[i] = f[i-1] + f[i-2]; 
        } 
        
        return f[n]; 
    } 
    
  
    public static void main (String args[]){ 
        int n = 6; 
        System.out.println(fn(n)); 
    } 
}
Output : 
8

More space-optimized Method

Algorithm

  1. Initialise three variable x=0, y=1, z.
  2. Traverse all the values till n starting from 2 one by one and update z as the sum of x and y, x=y, and y=z.
  3. Return y.

Time Complexity: O(n)     

Space Complexity: O(1)

C++ Program for Fibonacci numbers

#include<bits/stdc++.h>
using namespace std;

int fn(int n){ 
    int x=0, y=1, z;
    
    for(int i=2; i<=n; i++){ 
        z = x + y;
        x = y;
        y = z;
    } 
    
    return y; 
} 

int main (){ 
    int n = 6; 
    cout<<fn(n);
    return 0; 
}
Output :
8

Java Program for Fibonacci numbers

class fibNumbers{ 
    static int fn(int n){ 
        int x=0, y=1, z; 
        if(n == 0) 
            return x; 
        for(int i=2; i<=n; i++){ 
            z = x + y; 
            x = y; 
            y = z; 
        } 
        return y; 
    } 
  
    public static void main (String args[]){ 
        int n = 6; 
        System.out.println(fn(n)); 
    } 
}
Output :
8

Using Direct Formula

Here we’ll directly use the formula to find the nth Fibonacci number i.e.

Fn = ( ( ( (5 + 1) / 2) ^ n) / 5)

Time Complexity : O(1)     

Space Complexity : O(1)

C++ Program

#include<bits/stdc++.h>
using namespace std;

int fn(int n){ 
    double gr = (1 + sqrt(5)) / 2; 
    return round(pow(gr, n) / sqrt(5)); 
} 

int main (){ 
    int n = 6; 
    cout<<fn(n);
    return 0; 
}
Output :
8

Java Program

import java.util.*;

class fibNumbers{ 
    static int fn(int n){ 
        double gr = (1 + Math.sqrt(5)) / 2; 
        return (int) Math.round(Math.pow(gr, n) / Math.sqrt(5));
    } 
    
    public static void main (String args[]){ 
        int n = 6; 
        System.out.println(fn(n)); 
    } 
}
Output :
8

Reference

Interview Questions