C++ Examples

C++ Program - Fibonacci Sequence

Fibonacci terms are generally represented as F_n. A Fibonacci term is the sum of two previous terms and starts with 0 and 1. Mathematically, it can be represented as:

F_n = F_n-1 + F_n-2

With boundary conditions: F₀ = 0 and F₁ = 1

The Fibonacci Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

Method 1: Using Recursive function

In the example below, a recursive function called fib() is created to find out the nth term of Fibonacci sequence.

#include <iostream>
using namespace std;

static int fib(int);

static int fib(int n) {
  if (n == 0)
    {return 0;}
  else if (n == 1)
    {return 1;}
  else
    {return fib(n-1) + fib(n-2);}
}

int main() {
  cout<<"Fibonacci 5th term: "<<fib(5)<<"\n";
  cout<<"Fibonacci 6th term: "<<fib(6)<<"\n";
  cout<<"Fibonacci 7th term: "<<fib(7)<<"\n";
  return 0;
}

The above code will give the following output:

Fibonacci 5th term: 5
Fibonacci 6th term: 8
Fibonacci 7th term: 13

Method 2: Using Dynamic Programming

The Fibonacci term can also be estimated using dynamic programming. As compared to the recursive function, it calculates a specific term of the sequence only once.

#include <iostream>
using namespace std;

static int fib(int);

static int fib(int n) {
  //creating array which contains Fibonacci terms
  int f[n+1];
  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() {
  cout<<"Fibonacci 6th term: "<<fib(6)<<"\n";
  cout<<"Fibonacci 7th term: "<<fib(7)<<"\n";
  cout<<"Fibonacci 8th term: "<<fib(8)<<"\n";
  return 0;
}

The above code will give the following output:

Fibonacci 6th term: 8
Fibonacci 7th term: 13
Fibonacci 8th term: 21

Method 3: Using Ternary Operator

This can also be achieved using ternary operator.

#include <iostream>
using namespace std;

static int fib(int);

static int fib(int n) {
  int y = (n == 0)? 0 : (n == 1) ? 1 : fib(n-1) + fib(n-2);
  return y;
}

int main() {
  cout<<"Fibonacci 8th term: "<<fib(8)<<"\n";
  cout<<"Fibonacci 9th term: "<<fib(9)<<"\n";
  cout<<"Fibonacci 10th term: "<<fib(10)<<"\n"; 
  return 0;  
}

The above code will give the following output:

Fibonacci 8th term: 21
Fibonacci 9th term: 34
Fibonacci 10th term: 55

Method 4: Space optimized method

In this method, only three variables are used which changes in each iteration and finally nth term of Fibonacci Sequence is calculated.

#include <iostream>
using namespace std;

static int fib(int);

static int fib(int n) {
  int a = 0, b = 1, c = 0;
  if (n == 0)
    {return a;}
  for(int i = 2; i <= n; i++) {
    c = a + b;
    a = b;
    b = c;    
  }
  return b;
}

int main() {
  cout<<"Fibonacci 9th term: "<<fib(9)<<"\n";
  cout<<"Fibonacci 10th term: "<<fib(10)<<"\n";    
  cout<<"Fibonacci 11th term: "<<fib(11)<<"\n";
  return 0;
}

The above code will give the following output:

Fibonacci 9th term: 34
Fibonacci 10th term: 55
Fibonacci 11th term: 89

Method 5: Using power of matrix

A Fibonacci sequence term can also be calculated as power of matrix. A Fibonacci sequence holds below mentioned property:

To calculate F_n, power of matrix is calculated and A₀₁ will be the F_n.

#include <iostream>
using namespace std;

static int fib(int);

static int fib(int n) {
  int initial[2][2] = {{1,1},{1,0}};
  int Final[2][2] = {{1,1},{1,0}};
  int a, b, c, d;
  if (n == 0)
    {return 0;}
  else {      
    for(int i = 1; i < n ; i++) {
      a = Final[0][0]*initial[0][0] + Final[0][1]*initial[1][0];
      b = Final[1][0]*initial[0][0] + Final[1][1]*initial[1][0];
      c = Final[0][0]*initial[0][1] + Final[0][1]*initial[1][1];
      d = Final[1][0]*initial[0][1] + Final[1][1]*initial[1][1];
      Final[0][0] = a;
      Final[1][0] = b;
      Final[0][1] = c;
      Final[1][1] = d;           
    }
  }
  return Final[0][1];
}

int main() {
  cout<<"Fibonacci 10th term: "<<fib(10)<<"\n";    
  cout<<"Fibonacci 11th term: "<<fib(11)<<"\n";
  cout<<"Fibonacci 12th term: "<<fib(12)<<"\n";
  return 0;
}

The above code will give the following output:

Fibonacci 10th term: 55
Fibonacci 11th term: 89
Fibonacci 12th term: 144

C++ Program - Fibonacci Sequence

Method 1: Using Recursive function

Method 2: Using Dynamic Programming

Method 3: Using Ternary Operator

Method 4: Space optimized method

Method 5: Using power of matrix

Recommended Pages