C++ Program for Fibonacci Using Recursion

A C++ program for Fibonacci using recursion defines a function like int fibonacci(int n) { if (n <= 1) return n; else return fibonacci(n-1) + fibonacci(n-2); } and calls it to get Fibonacci numbers.

Examples

Input0

OutputFibonacci(0) = 0

Input5

OutputFibonacci(5) = 5

Input10

OutputFibonacci(10) = 55

How to Think About It

To find the Fibonacci number at position n, check if n is 0 or 1 and return n directly. Otherwise, calculate it by adding the Fibonacci numbers at positions n-1 and n-2 using the same function recursively.

Algorithm

1

Get the input number n.

2

If n is 0 or 1, return n as the Fibonacci number.

3

Otherwise, call the function recursively for n-1 and n-2.

4

Add the results of the two recursive calls.

5

Return the sum as the Fibonacci number for n.

Code

cpp

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 10;
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

Output

Fibonacci(10) = 55

Dry Run

Let's trace fibonacci(5) through the code

1

Call fibonacci(5)

Since 5 > 1, call fibonacci(4) + fibonacci(3)

2

Call fibonacci(4)

Since 4 > 1, call fibonacci(3) + fibonacci(2)

3

Call fibonacci(3)

Since 3 > 1, call fibonacci(2) + fibonacci(1)

4

Call fibonacci(2)

Since 2 > 1, call fibonacci(1) + fibonacci(0)

5

Base cases

fibonacci(1) returns 1, fibonacci(0) returns 0

6

Calculate fibonacci(2)

1 + 0 = 1

7

Calculate fibonacci(3)

fibonacci(2) + fibonacci(1) = 1 + 1 = 2

8

Calculate fibonacci(4)

fibonacci(3) + fibonacci(2) = 2 + 1 = 3

9

Calculate fibonacci(5)

fibonacci(4) + fibonacci(3) = 3 + 2 = 5

Call	Return Value
fibonacci(1)	1
fibonacci(0)	0
fibonacci(2)	1
fibonacci(3)	2
fibonacci(4)	3
fibonacci(5)	5

Why This Works

Step 1: Base Case

The function returns n directly when n is 0 or 1 to stop recursion.

Step 2: Recursive Calls

For other values, the function calls itself twice with n-1 and n-2 to build the Fibonacci sequence.

Step 3: Combining Results

The results of the two recursive calls are added to get the Fibonacci number at position n.

Alternative Approaches

Iterative approach

cpp

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n = 10;
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

This method uses a loop and is faster and uses less memory than recursion.

Memoization (Top-down DP)

cpp

#include <iostream>
#include <vector>
using namespace std;

int fibonacci(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo);
    return memo[n];
}

int main() {
    int n = 10;
    vector<int> memo(n+1, -1);
    cout << "Fibonacci(" << n << ") = " << fibonacci(n, memo) << endl;
    return 0;
}

This method stores results to avoid repeated calculations, improving speed over plain recursion.

Complexity: O(2^n) time, O(n) space

Time Complexity

The recursive function calls itself twice for each non-base case, leading to exponential time O(2^n).

Space Complexity

The maximum depth of the recursion stack is n, so space complexity is O(n).

Which Approach is Fastest?

Iterative and memoized methods run in O(n) time, much faster than plain recursion.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Learning recursion, small n
Iterative	O(n)	O(1)	Efficient calculation, large n
Memoization	O(n)	O(n)	Efficient recursion with caching