Fibonacci

The Fibonacci sequence demonstrates tree-like recursion where each call spawns multiple recursive calls.

Understanding Fibonacci

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Each number is the sum of the two preceding ones:

fib(n) = fib(n-1) + fib(n-2)

Base Cases

fib(0) = 0, fib(1) = 1

Recursive Case

fib(n) = fib(n-1) + fib(n-2)

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

Fibonacci Call Tree

Calculate fibonacci(n): 5

Total Calls

Duplicate Calculations

Result

Unique calculation

Duplicate (wasted work)

Wasted Calculations:

fib(1) called 5 timesfib(2) called 3 timesfib(0) called 3 timesfib(3) called 2 times

Exponential Growth Warning!

This naive recursive implementation is O(2^n). Look how fast it grows:

fib(5): 15 callsfib(10): 177 callsfib(15): 1,973 callsfib(20): 21,891 callsfib(25): 242,785 callsfib(30): 2,692,537 calls

fib(30) makes over 2.6 million calls! This is why we need memoization or iteration.

Common Recursion Pitfalls

Pitfall 1: Missing Base Case

// BAD: No base case = infinite recursion!
int badFactorial(int n) {
    return n * badFactorial(n - 1);  // Never stops!
}

// This will crash with StackOverflowError

Fix: Always include a base case that returns without recursing.

Pitfall 2: Base Case Never Reached

// BAD: Recursion doesn't progress toward base case
int badSum(int n) {
    if (n == 0) return 0;
    return n + badSum(n);  // n never changes!
}

// This will also crash - n stays the same forever

Fix: Ensure the recursive call moves toward the base case (e.g., n-1 not n).

Pitfall 3: Stack Overflow from Deep Recursion

// This code is CORRECT but will crash for large n
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

factorial(100000);  // StackOverflowError!
// The stack can only hold ~10,000 frames

Fix: Use iteration for very large inputs, or use tail recursion (if supported).

Why Naive Fibonacci is Inefficient

The tree visualization above shows the problem: repeated calculations.

The Problem: Exponential Time Complexity O(2^n)

For fib(5), we calculate fib(2) three times and fib(3) twice! As n grows, the wasted work grows exponentially.

n	Total Calls	Time (approx)
10	177	instant
20	21,891	instant
30	2,692,537	~1 second
40	331,160,281	~1 minute
50	40+ billion	~2 hours

The Solution: Memoization or Iteration

By storing previously calculated values (memoization) or using a simple loop, we can reduce this to O(n) time. We'll compare approaches on the next page!