Next
1. Factorial using Recursion2. Fibonacci using Recursion3. Tower of Hanoi4. GCD using Recursion5. Power using Recursion

Fibonacci using Recursion in C++

Fibonacci Series using Recursion in C++.

BeginnerRecursion ProgramsExample 2 of 5
fibonacci-using-recursion.cpp
1#include <iostream>
2using namespace std;
3

4// Recursive function to calculate Fibonacci number
5int fibonacci(int n) {
6    // Base cases
7    if (n == 0) {
8        return 0;
9    }
10    if (n == 1) {
11        return 1;
12    }
13    
14    // Recursive case
15    return fibonacci(n - 1) + fibonacci(n - 2);
16}
17

18int main() {
19    int terms;
20    cout << "Enter number of terms: ";
21    cin >> terms;
22    
23    if (terms < 0) {
24        cout << "Invalid input." << endl;
25        return 1;
26    }
27    
28    cout << "Fibonacci series:" << endl;
29    for (int i = 0; i < terms; i++) {
30        cout << fibonacci(i) << " ";
31    }
32    cout << endl;
33    
34    // Show individual Fibonacci numbers
35    cout << "\nIndividual Fibonacci numbers:" << endl;
36    for (int i = 0; i <= 10; i++) {
37        cout << "F(" << i << ") = " << fibonacci(i) << endl;
38    }
39    
40    return 0;
41}

Output

Enter number of terms: 10
Fibonacci series:
0 1 1 2 3 5 8 13 21 34

Individual Fibonacci numbers:
F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

What's going on

The program demonstrates recursive Fibonacci calculation:

Recursive function with multiple base cases
Calculating Fibonacci numbers
Generating Fibonacci series
Understanding recursive structure

Recursion provides intuitive solution for Fibonacci sequence.

Header Files Used

1.#include <iostream>
Provides cout and cin for input/output operations.

Understanding Fibonacci Sequence

Fibonacci Definition

:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n > 1

Sequence

:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Each number = sum of previous two
Appears in nature, mathematics, art

Multiple Base Cases

Base Cases

:

if (n == 0) {

}

if (n == 1) {

return 1;

}

1return 0;

How it works

:

Two base cases needed
F(0) = 0, F(1) = 1
Stops recursion
Returns known values

Recursive Case

Function Calls Itself

:

1return fibonacci(n - 1) + fibonacci(n - 2);

How it works

:

Calls fibonacci(n-1) and fibonacci(n-2)
Adds results together
Reduces problem to smaller subproblems
Builds solution from base cases

Recursion Flow

Example: fibonacci(5)

:

1.fibonacci(5) = fibonacci(4) + fibonacci(3)
2.fibonacci(4) = fibonacci(3) + fibonacci(2)
3.fibonacci(3) = fibonacci(2) + fibonacci(1)
4.fibonacci(2) = fibonacci(1) + fibonacci(0)
5.Base cases return: F(1)=1, F(0)=0
6.Results propagate back: F(2)=1, F(3)=2, F(4)=3, F(5)=5

Performance Consideration

Time Complexity

:

O(2^n) - exponential
Repeated calculations
Same values calculated multiple times
Inefficient for large n

Optimization

:

Memoization: cache results
Iterative: O(n) time
Dynamic programming: store computed values
Better for large n

When to Use Recursive Fibonacci

Best For

:

Learning recursion
Small values of n
Understanding recursive structure
Educational purposes

Not Recommended For

:

Large values of n
Performance-critical code
Production applications
Real-time systems

Important Considerations

Base Cases

:

Must have both F(0) and F(1)
Stops recursion properly
Prevents infinite recursion
Essential for correctness

Stack Overflow

:

Deep recursion uses stack
May overflow for large n
Consider iterative approach
Limited by stack size

Repeated Calculations

:

Same values calculated multiple times
Inefficient recursive tree
Memoization improves performance
Trade-off: simplicity vs efficiency

return 0;

This ends the program successfully.

PreviousFactorial using RecursionNextTower of Hanoi