Fibonacci Series Program in C (Recursion)
In this method, we will use a function that prints the first two terms, and the rest of the terms are then handled by the other function that makes use of a recursive technique to print the next terms of the sequence.
C
// C Program to print the Fibonacci series using recursion#include <stdio.h>// first two valuesint prev1 = 1;int prev2 = 0;// recursive function to print the fibonacci seriesvoid fib(int n){ if (n < 3) { return; } int fn = prev1 + prev2; prev2 = prev1; prev1 = fn; printf("%d ", fn); return fib(n - 1);}// function that handles the first two terms and calls the// recursive functionvoid printFib(int n){ // when the number of terms is less than 1 if (n < 1) { printf("Invalid number of terms\n"); } // when the number of terms is 1 else if (n == 1) { printf("%d ", 0); } // when the number of terms is 2 else if (n == 2) { printf("%d %d", 0, 1); } // number of terms greater than 2 else { printf("%d %d ", 0, 1); fib(n); } return;}// driver codeint main(){ int n = 9; printFib(n); return 0;} |
Output
0 1 1 2 3 5 8 13 21
Complexity Analysis
Time complexity: O(n), It is because, for printing n terms, the fib() function will call itself recursively for (n – 2) times and each time it will take constant time.
Space Complexity: O(n), It is because, for each recursive call of the fib() function, a separate stack frame is created. For (n-2) calls, (n-2) stack frames are created with results in the O(n) space complexity.
Fibonacci Series Program in C
In this article, we will discuss the Fibonacci series and the programs to print the Fibonacci series in C using recursion or loops.