Fibonacci Series
Published by: Anil K. Panta
The Fibonacci series is a popular number sequence in mathematics and computer science. It is used in many real-world problems, including programming, biology, and design patterns.
Let’s learn how to generate the Fibonacci series using recursion, and understand the algorithm and C program behind it.
What is the Fibonacci Series?
The Fibonacci series is formed by adding the two previous numbers in the sequence:
F(n) = F(n – 1) + F(n – 2)
With starting values:
F(0) = 0
F(1) = 1
Example:
F(5) = 0 1 1 2 3
F(8) = 0 1 1 2 3 5 8 13
What is Recursion?
Recursion is a process where a function calls itself to solve smaller parts of the same problem.
In the Fibonacci series, recursion works perfectly because F(n) depends on F(n - 1) and F(n - 2) — smaller versions of the same problem.
Algorithm: Fibonacci Series Using Recursion
Step 1: Start
Step 2: Define a function `fibonacci(n)`
If n == 0, return 0
If n == 1, return 1
Else return fibonacci(n - 1) + fibonacci(n - 2)
Step 3: In the main function:
- Read the number of terms to generate
- Loop from i = 0 to n-1
- Call fibonacci(i) and print the result
Step 4: End
C Program: Fibonacci Series Using Recursion
#include <stdio.h>
int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 5;
printf("Number is: %d\n", n);
printf("Fibonacci series up to number %d is: ", n);
for(int i = 0; i < n; i++) {
printf("%d ", fibonacci(i));
}
return 0;
}
Output:
Number is: 5
Fibonacci series up to number 5 is: 0 1 1 2 3
Iterative Version (for Comparison)
void fibonacciIterative(int n) {
int f0 = 0, f1 = 1, fib;
printf("%d %d ", f0, f1);
for (int i = 2; i < n; i++) {
fib = f0 + f1;
printf("%d ", fib);
f0 = f1;
f1 = fib;
}
}
Time & Space Complexity
Summary: Recursion vs Iteration for Fibonacci
Final Thought
Fibonacci using recursion helps build strong problem-solving skills. It's a great example to understand how recursive functions work and how problems can be broken down into smaller parts.
