Coding Exercise: Fibonacci Sequence Using Recursion

Calculate nth Fibonacci number where F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).

Test cases: fib(6)=8, fib(7)=13, fib(0)=0.

Problem Statement

Input: Integer n (0 ≤ n ≤ 20)

Output: F(n) - nth Fibonacci number

Base cases: F(0)=0, F(1)=1

Recursive: F(n)=F(n-1)+F(n-2)

Sequence: 0,1,1,2,3,5,8,13,21,34...

Approach

1. Base cases: if n==0 return 0, if n==1 return 1

2. Recursive: return fib(n-1) + fib(n-2)

3. Two branches create tree-like recursion

Solution Code

#include <iostream>
using namespace std;

int fibonacci(int n) {
    // Base cases
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // Recursive case
    return fibonacci(n-1) + fibonacci(n-2);
}

int main() {
    int num;
    cout << "Enter position: ";
    cin >> num;
    
    cout << "F(" << num << ") = " << fibonacci(num) << endl;
    return 0;
}

Dry Run: fibonacci(5)

fib(5)
├── fib(4) + fib(3)
│   ├── fib(3) + fib(2)
│   │   ├── fib(2) + fib(1) = 1 + 1 = 2
│   │   └── fib(1) = 1
│   └── fib(2) = 2
└── fib(3) = 3

Result: 5 + 3 = 8 ✓

Test Cases

n=0  → F(0)=0
n=1  → F(1)=1
n=2  → F(2)=1
n=5  → F(5)=5
n=6  → F(6)=8
n=7  → F(7)=13

Time & Space Analysis

Time: O(2^n) - exponential (fib tree)

Space: O(n) - max recursion depth

Optimization: Memoization or iteration for production

Practice Variations

1. Print first N Fibonacci numbers

2. Check if number is Fibonacci

3. Fibonacci with memoization (DP)

Conclusion

Mastered Fibonacci recursion! Understand exponential complexity.

Next: Power function or string reversal recursively.