Introduction

A common confusion is whether naive recursive Fibonacci runs in O(2^n) or O(n^2). The correct growth is exponential because recursion branches into two calls at most levels. Understanding the recursion tree makes the complexity argument straightforward.

Why Naive Recursion Grows Exponentially

The classic recursive function is F(n) = F(n-1) + F(n-2) with base cases for small n. Runtime follows a similar recurrence: T(n) = T(n-1) + T(n-2) + O(1).

That recurrence is dominated by Fibonacci growth itself, which is proportional to phi^n, where phi is approximately 1.618. Since phi^n is bounded above by 2^n, complexity is often written as O(2^n) for simplicity.

1def fib_naive(n):
2    if n <= 1:
3        return n
4    return fib_naive(n - 1) + fib_naive(n - 2)
5
6for i in range(10):
7    print(i, fib_naive(i))

The repeated subproblem expansion is the root cause. For example, fib_naive(5) computes fib_naive(3) more than once.

Why It Is Not O(n^2)

O(n^2) suggests polynomial growth where doubling input roughly multiplies work by about four. Naive Fibonacci grows far faster: each increment in n adds a branching layer in the recursion tree.

You can observe this by counting function calls.

1call_count = 0
2
3def fib_counted(n):
4    global call_count
5    call_count += 1
6    if n <= 1:
7        return n
8    return fib_counted(n - 1) + fib_counted(n - 2)
9
10for n in [10, 20, 30]:
11    call_count = 0
12    fib_counted(n)
13    print(f"n={n}, calls={call_count}")

Call counts increase dramatically, demonstrating exponential behavior rather than polynomial growth.

Optimized Approaches and Their Complexities

Memoization stores computed values and turns recursion into linear-time dynamic programming. Iterative DP does the same with constant auxiliary space.

1def fib_memo(n, memo=None):
2    if memo is None:
3        memo = {}
4    if n in memo:
5        return memo[n]
6    if n <= 1:
7        return n
8    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
9    return memo[n]
10
11
12def fib_iter(n):
13    if n <= 1:
14        return n
15    a, b = 0, 1
16    for _ in range(2, n + 1):
17        a, b = b, a + b
18    return b
19
20print(fib_memo(50))
21print(fib_iter(50))

Complexities:

• Naive recursion: exponential, often written O(2^n).
• Memoized recursion: O(n) time and O(n) space.
• Iterative DP: O(n) time and O(1) extra space.

Intuition You Can Reuse

Whenever recursion spawns multiple branches with overlapping subproblems and no caching, suspect exponential runtime. Whenever each state is solved once and reused, runtime often drops to linear or near-linear in number of states.

This reasoning pattern applies far beyond Fibonacci and is useful for many interview and production algorithm decisions.

Recurrence Intuition with the Call Tree

A call tree view makes complexity intuitive. At level zero, one call exists. At the next level, there are roughly two calls. At subsequent levels, branch count continues growing until base cases terminate recursion. Although branching is not perfectly full near leaves, total nodes still track Fibonacci growth closely. This growth rate is super-polynomial relative to n^2, which is why naive recursion becomes impractical quickly. For example, increasing n from 30 to 40 can multiply runtime by an order of magnitude, not by a small quadratic factor. When teaching complexity, pair recurrence equations with empirical call counts so the conceptual and observed behavior match. This dual perspective helps avoid memorized but misunderstood complexity claims.

1for n in range(25, 36, 5):
2    call_count = 0
3    fib_counted(n)
4    print("n", n, "calls", call_count)

Common Pitfalls

• Confusing recursive depth n with total number of recursive calls.
• Assuming two recursive calls imply quadratic runtime automatically.
• Ignoring overlapping subproblems when analyzing recurrences.
• Benchmarking only tiny n and drawing incorrect complexity conclusions.

Summary

• Naive Fibonacci recursion is exponential, commonly expressed as O(2^n).
• It is not quadratic because recursive call count grows much faster than n^2.
• Memoization converts repeated work into one-time state computation.
• Iterative DP provides linear time with constant extra space.
• Complexity analysis should focus on total work, not only recursion depth.