Why Naive Fibonacci Is Exponential

Visualize the recursion tree, repeated subproblems, and why memoization or dynamic programming removes the wasted work.

Choose n
Drag the slider and watch the call tree grow.
Current input
n = 6
F(n)
8
Recursive calls
25
Unique subproblems
7
Repeated calls
18
Recursive call tree
Repeated F(k) nodes show exactly where the wasted work comes from.
Why the runtime becomes exponential
T(n) ≈ T(n−1) + T(n−2) + O(1)

Every non-base call creates two more calls. The number of calls therefore grows with essentially the same recurrence as the Fibonacci sequence itself.

Time: Θ(φn), where φ ≈ 1.618

Space: O(n), because the deepest recursion path is n → n−1 → ... → 1.

The key repeated subproblem
Interview insight: if recursion branches and different branches repeatedly ask for the same state, think memoization or dynamic programming.
Four ways to compute F(n)
Naive recursion
O(φn)
Huge recursion tree
Memoization
O(n)
Compute each F(k) once
Bottom-up DP
O(n)
Keep only the previous two values
Fast doubling
O(log n)
Reduce the input by roughly half each step
How to come up with this in an interview
1. Draw a tiny recursion tree

Expand F(5). You immediately see F(3), F(2), and other states repeated.

2. Write the time recurrence

T(n)=T(n−1)+T(n−2)+O(1). That has Fibonacci-like growth, so the runtime is exponential.

3. Remove duplicate states

Cache each F(k) or compute values iteratively. Now every state is solved once, giving O(n).

Bottom-up implementation
def fibonacci_dp(n):
    if n <= 1:
        return n

    a, b = 0, 1

    for _ in range(2, n + 1):
        a, b = b, a + b

    return b