Overview
Recursive Fibonacci computes fib(n) = fib(n-1) + fib(n-2) following the mathematical definition directly.
Analogy
Asking two friends for help, each of whom asks two more friends — the work explodes exponentially.
Step-by-step
- Base cases: fib(0)=0, fib(1)=1.
- Recursive case: return fib(n-1) + fib(n-2).
- Each call spawns two more until base cases hit.
Visual
fib(4) → fib(3)+fib(2) → (fib(2)+fib(1))+(fib(1)+fib(0)) → ...
Common mistakes
- Missing base cases causing infinite recursion.
- Not realizing it's exponential O(2^n) without memoization.
Practice questions
- Add @functools.lru_cache to make it O(n).
- Draw the call tree for fib(5) and count duplicate calls.
Time
O(2^n) naive, O(n) with memoization
AI Wisdom