Introduction

The space complexity of the naive recursive Fibonacci algorithm is O(n), not O(2^n). That answer surprises people because the time complexity is exponential, but space is governed by the maximum recursion depth rather than the total number of calls. This article explains why the stack grows linearly, what changes with memoization, and how to reason about recursion space correctly.

The Naive Recursive Algorithm

The classic textbook Fibonacci implementation looks like this:

1def fib(n: int) -> int:
2    if n <= 1:
3        return n
4    return fib(n - 1) + fib(n - 2)
5
6
7print(fib(6))

This creates a large recursion tree, but the key space question is how many frames exist simultaneously on the call stack.

Why the Space Complexity Is O(n)

At any instant, the deepest active chain of calls looks like:

• 'fib(n)'
• 'fib(n - 1)'
• 'fib(n - 2)'
• and so on down to the base case

That chain has depth proportional to n, so the maximum stack memory is linear in n.

The total number of calls is much larger, but most of those calls do not coexist on the stack at the same time. They happen one after another as recursion unwinds and branches.

Time Complexity and Space Complexity Are Different

This is the common confusion point.

For naive recursion:

• time complexity is exponential, often written as O(phi^n) or loosely O(2^n)
• space complexity is O(n)

The call tree is huge, but only one root-to-leaf path is active at once plus some pending frames waiting for sibling results.

Visualizing the Call Stack

Take fib(5):

1fib(5)
2  fib(4)
3    fib(3)
4      fib(2)
5        fib(1)

Before the stack can grow further, it hits a base case and begins returning. Then other branches are explored. The depth never becomes larger than a constant multiple of n, which is why the space stays linear.

A Small Instrumented Example

You can track depth directly to see the maximum stack height.

1def fib_with_depth(n: int, depth: int = 1) -> tuple[int, int]:
2    if n <= 1:
3        return n, depth
4
5    left_value, left_depth = fib_with_depth(n - 1, depth + 1)
6    right_value, right_depth = fib_with_depth(n - 2, depth + 1)
7
8    return left_value + right_value, max(left_depth, right_depth)
9
10
11value, max_depth = fib_with_depth(6)
12print(value)
13print(max_depth)

The total call count grows fast, but the maximum depth grows only linearly.

Memoized Recursion Still Uses Stack Space

If you add memoization, the time complexity improves dramatically, but recursive stack space is still O(n) because the recursion depth can still reach n.

1from functools import lru_cache
2
3@lru_cache(maxsize=None)
4def fib(n: int) -> int:
5    if n <= 1:
6        return n
7    return fib(n - 1) + fib(n - 2)

Now the algorithm uses:

• 'O(n) stack space from recursion depth'
• plus O(n) memo table space for cached results

So overall auxiliary memory is still linear, just for different reasons than the naive version.

Iterative Fibonacci Uses Less Stack Space

An iterative implementation avoids recursion depth entirely.

1def fib_iter(n: int) -> int:
2    if n <= 1:
3        return n
4
5    a, b = 0, 1
6    for _ in range(2, n + 1):
7        a, b = b, a + b
8    return b
9
10
11print(fib_iter(6))

This version runs in O(n) time and O(1) extra space, which is one reason it is usually preferred in production code.

Recursive Definitions Do Not Automatically Mean Exponential Space

Another useful lesson is broader than Fibonacci. Recursive algorithms often get overestimated on space because people confuse tree size with stack depth.

To estimate recursive space, ask:

• how deep can the recursion go before returning
• how much memory does each frame use
• is extra storage such as memoization or temporary arrays involved

That reasoning is much more reliable than looking at the total number of recursive calls.

Common Pitfalls

• Answering O(2^n) for space because the recursion tree has exponentially many nodes.
• Confusing total calls with simultaneous stack frames.
• Forgetting to count memo tables when memoization is added.
• Assuming every recursive algorithm has the same space characteristics.
• Ignoring the constant-space iterative alternative when performance matters.

Summary

• The naive recursive Fibonacci algorithm uses O(n) space because stack depth grows linearly.
• Its time complexity is exponential, but time and space are different measures.
• Memoized recursion still uses linear stack depth plus linear cache space.
• An iterative Fibonacci solution can reduce extra space to O(1).
• For recursive complexity questions, focus on maximum active depth, not total tree size.