Overview
Recursion is the paradigm where a function solves a problem by calling itself on smaller inputs, until it reaches a base case that can be answered directly. Naive Fibonacci — fib(n) = fib(n−1) + fib(n−2) — is the textbook illustration.
Each call branches into two more, so the naive recursion draws an exponentially growing call tree that recomputes the same subproblems over and over. That waste is exactly what memoization and dynamic programming set out to fix.
How Recursion works
- Define a base case: fib(0) = 0 and fib(1) = 1 return immediately.
- For any larger n, the call spawns two child calls, fib(n−1) and fib(n−2).
- Follow the tree down the leftmost branch until it bottoms out at a base case.
- As each call returns, its value bubbles up and combines with its sibling until the root fib(n) is known.
When to use it
- Problems with a naturally self-similar structure — trees, nested data, and divide-and-conquer.
- Writing clear, declarative solutions that mirror a recurrence relation directly.
- Avoid naive recursion when subproblems overlap — add memoization or switch to iteration.
Complexity analysis
Naive Fibonacci makes roughly φ^n calls (φ ≈ 1.618), so its running time is O(φ^n) — exponential, near O(2^n). The recursion also uses O(n) stack space for the deepest branch. The blow-up comes purely from recomputing overlapping subproblems.
Frequently asked questions
Why is naive recursive Fibonacci so slow?
Because it recomputes the same subproblems: fib(5) evaluates fib(3) twice, fib(2) three times, and so on, producing an exponential number of calls. Caching results collapses it to linear time.
What is a base case and why is it essential?
The base case is the smallest input answered without further recursion. Without it the calls never stop, causing infinite recursion and a stack overflow.