Fibonacci series

Recursion code for Fibonacci series

To take the program of printing the Fibonacci series to the next level, we will be doing the same task but with the help of recursion. Recursion is when a function calls itself again and again until its base case gets hit. Code is given below for the same.

Fibonacci series can be programed using recursion:-

#include <iostream>
using namespace std;
 
int fib(int n) {
   if((n==0)||(n==1)) {
      return(n);
   }else {
      return(fib(n-1)+fib(n-2));
   }
}
int main() {
   int i=0;
   cout << "\nFibonacci Series upto 10 terms :- "<<endl;
   while(i < 10) {
      cout << " " << fib(i);
      i++;
   }
   return 0;
}

Output :

Fibonacci Series upto 10 terms:-
 0 1 1 2 3 5 8 13 21 34

Time complexity of the above code is O(n) and space complexity is O(1).

In the above piece of code, the program starts running from the main() function, and after taking the input from the user, the fibo() function gets called. Inside the fibo() function, it first checks whether 'n' is less than or equal to 1 and if it is true, then returns else continues in the function. Later in the same function, there are two calls for the same function (function itself) for n-1 and n-2. It returns the sum of the returned value of previous function call statements. 

Also see, fibonacci series in c

Dynamic programming code for Fibonacci series

Recursion is good, but multiple irrelevant calls are made during recursion. So to make code more efficient, we use dynamic programming to achieve our task. We will print the Fibonacci series with the help of dynamic programming, i.e., dp. Code is given below.

#include<iostream>
using namespace std;

void fibonacci(int n) {
   int fibo[n+1];
   fibo[0] = 0;
   fibo[1] = 1;
   for (int i = 2; i <= n; i++) {
      fibo[i] = fibo[i-1] + fibo[i-2]; 
   }

   for(int j =0; j<n+1; j++)
        cout << fibo[j] << " ";
}

int main () {
    cout <<"Fibonacci Terms upto 10 terms :- "<<endl;
    fibonacci(10);
    return 0;
}

Output :

Fibonacci Series upto 10 terms:-
0 1 1 2 3 5 8 13 21 34

Time complexity of the above code is O(n) and space complexity is O(1).

We use dynamic programming to print the Fibonacci series in the above code. In the function fibonacci(), the first statement is a way to declare a dynamic array in C++, and here its length is one more than the user-entered value. Its size is one more because it has to hold the values from  0 to n, making a total n+1. After declaring the array, we add 0 and 1 in the 0th and 1st index of the same array. Then with the help of a for loop, we retrieve the value of the previous two values stored in dp, compute the current ith value, and return the final array. There is a simple print statement in the main() function to print the returned array from the function fibo(). 

Also read -  Decimal to Binary c++

FAQs

1. What is the Fibonacci sequence?
   The Fibonacci series is the sequence of numbers in the form of 0 1 1 2 3 5 8 13 and so on.
    
2. Can we print only the nth value of the Fibonacci series?
   Yes, by changing a few lines of the program, you can directly print the nth value of the series.
    
3. While writing a dynamic programming program of the Fibonacci series, why do we take the size of dp as n+1?
   The size of dp must be taken as n+1 because we need to calculate and store the nth value of the Fibonacci series in the dp array.

Key Takeaways

In this article, we have extensively discussed the Fibonacci series and its implementation in C++. The blog contains the basic definition of the Fibonacci series and its implementation. Program to print this sequence will require a for or while loop. The dynamic programming method will be more helpful in making code more effective.

Check out this problem - Frog Jump

We hope that this blog has helped you enhance your knowledge regarding printing the Fibonacci series and if you would like to learn more, check out our articles on the Fibonacci sequence in Java. Do upvote our blog to help other ninjas grow. Happy Coding!