Write a C program to print Fibonacci Series using recursion. Given an input number, we have to write a code to print Fibonacci series up to that number using Recursion.
This question is very important in terms of technical interviews.
You can check my previous post for PHP script to print Fibonacci series. Before solving this problem, Let’s first understand what is Recursion?
What is Recursion?
In recursion, A function calls itself until the base condition is reached. Recursive code is much cleaner and shorter as compared to iterative code.
For better understanding you can check my previous post on recursion and what’s the difference between recursion and iteration.
For better understanding of recursion concept, you can solve Objective Question on Recursion.
C Program to Print Fibonacci Series using Recursion
What is Fibonacci Series?
In Fibonacci series, the first two numbers are 0 and 1 and each subsequent number is the sum of previous two numbers.
0 ,1 , 1, 2, 3, 5, 8, 13, 21 ……………….
In mathematical terms, the Nth term of Fibonacci numbers is defined by the recurrence relation.
- fibonacci(N) = fibonacci(N – 1) + fibonacci(N – 2)
- whereas fibonacci(0) = 0 and fibonacci(1) = 1
C Program to Print Fibonacci Series using Recursion
We have learned about Fibonacci series and it’s mathematical recurrence relation. Let’s write a C program to generate Fibonacci series upto N numbers using recursion.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/* C Program to Print Fibonacci Series upto N numbers using Recursion */ #include <stdio.h> int fibonacci(int num){ if(num == 0) { return 0; } else if(num == 1) { return 1; } else { //recursive call return (fibonacci(num-1) + fibonacci(num-2)); } } main() { /* Assume we want to print first six number of Fibonacci series. */ int num; printf("Enter a number"); scanf("%d", &num); for(int i = 0; i < num; i++) { /* Call fibonacci function. */ printf(" %d ",fibonacci(i)); } } |
Program Logic
1. Return 0 if the input number is 0, 1 if the input number is 1.
2. If number is greater than 1 then return func(n-1) + func(n-2). func is the name of a function.
Explanation – Suppose an input number is 4.
|
1 |
/* When 4 is input, as per else condition. */ |
fibonacci(3) + fibonacci(2) /* fibonacci(3) and fibonacci(2), calls function */ (fibonacci(1) + fibonacci (2)) + (fibonacci(0) + fibonacci(1)) 1 + (fibonacci (1) + fibonacci (0) ) + 0 + 1 1 + 1 + 1 3
The Fourth element of Fibonacci series is 3. Similarly, other elements are printed in the same way.
