# Space Complexity Comparison: Recursive vs Iterative Implementations in Hello-Algo

> Compare space complexity of recursive vs iterative algorithms. See how hello algo stacks up with O(n) call stack vs O(1) auxiliary space.

- Repository: [Yudong Jin/hello-algo](https://github.com/krahets/hello-algo)
- Tags: performance
- Published: 2026-02-25

---

**Recursive algorithms in the hello-algo repository consume O(n) call-stack space for depth-n problems, while equivalent iterative implementations use O(1) constant auxiliary space, as demonstrated side-by-side in the computational complexity chapter.**

The krahets/hello-algo repository provides parallel implementations of classic algorithms in both recursive and iterative forms, making it an ideal reference for analyzing their memory footprints. By examining the source files in `codes/python/chapter_computational_complexity/`, developers can see exactly how call-stack frames and explicit data structures contribute to space complexity.

## O(n) Call Stack vs. O(1) Constant Space

The fundamental difference lies in how each approach manages execution state during computation.

### Plain Recursion and Call Stack Overhead

In [`recursion.py`](https://github.com/krahets/hello-algo/blob/main/recursion.py), the `recur` function and `linear_recur` in [`space_complexity.py`](https://github.com/krahets/hello-algo/blob/main/space_complexity.py) demonstrate how each recursive call adds a new frame to the Python interpreter’s call stack. For a recursion depth of `n`, this results in **O(n) extra space** usage, as every frame stores local variables and return addresses.

```python
def recur_sum(n: int) -> int:
    if n == 1:
        return 1
    return n + recur_sum(n - 1)  # O(n) call stack frames

```

Notably, CPython lacks tail-call optimization, so even the `tail_recur` implementation in [`recursion.py`](https://github.com/krahets/hello-algo/blob/main/recursion.py) still consumes O(n) stack space rather than the O(1) that tail recursion theoretically allows in other languages.

### Pure Iteration with Constant Memory

The `for_loop` and `while_loop` functions in [`iteration.py`](https://github.com/krahets/hello-algo/blob/main/iteration.py) solve identical problems using only loop variables and accumulators. Because these algorithms do not rely on the call stack to maintain state, they require **O(1) constant space** regardless of input size.

```python
def iter_sum(n: int) -> int:
    total = 0
    for i in range(1, n + 1):
        total += i  # O(1) extra space

    return total

```

### Explicit Stack Simulation

The `for_loop_recur` function in [`recursion.py`](https://github.com/krahets/hello-algo/blob/main/recursion.py) offers a hybrid approach: it simulates recursion using an explicit Python `list` as a stack. While this still requires **O(n) space** to hold the simulated frames, it transfers memory management from the interpreter’s hidden call stack to a visible, user-controlled data structure.

```python
def stack_sum(n: int) -> int:
    stack = list(range(n, 0, -1))  # O(n) explicit stack

    total = 0
    while stack:
        total += stack.pop()
    return total

```

## When Recursion Dominates Space Usage

Beyond linear call-stack growth, certain recursive patterns in hello-algo exhibit polynomial or exponential space complexity due to data allocation within each frame.

### Exponential Space in Tree Construction

The `build_tree` function in [`space_complexity.py`](https://github.com/krahets/hello-algo/blob/main/space_complexity.py) constructs a complete binary tree of height `n`. While the recursion depth contributes O(n) stack space, the total space complexity is dominated by the **O(2ⁿ) TreeNode objects** created and retained throughout execution.

```python
def build_tree(n: int) -> TreeNode | None:
    if n == 0:
        return None
    root = TreeNode(0)
    root.left = build_tree(n - 1)   # creates left subtree

    root.right = build_tree(n - 1)  # creates right subtree

    return root  # total nodes ≈ 2ⁿ

```

### Quadratic Space Allocation

The `quadratic_recur` function demonstrates a worst-case scenario where each recursive call allocates a new array. With call depths from `n` down to `1`, and arrays sized `n`, `n-1`, ..., `1`, the cumulative memory usage reaches **O(n²)**.

```python
def quadratic_recur(n: int) -> int:
    if n <= 0:
        return 0
    nums = [0] * n  # O(n) allocation per call

    return quadratic_recur(n - 1)  # cumulative O(n²)

```

## Practical Code Comparison

Running the implementations from [`recursion.py`](https://github.com/krahets/hello-algo/blob/main/recursion.py) and [`iteration.py`](https://github.com/krahets/hello-algo/blob/main/iteration.py) illustrates the practical memory differences. The recursive `recur_sum` will hit Python’s recursion limit for large `n` due to stack exhaustion, while `iter_sum` handles arbitrarily large inputs with constant memory overhead.

For algorithms requiring backtracking or tree traversal, the explicit stack approach (as seen in `for_loop_recur`) provides the logical clarity of recursion with the memory predictability of iteration, though it still requires O(n) auxiliary space.

## Summary

- **Plain recursion** incurs **O(n)** space complexity from call-stack frames in CPython, as shown in [`recursion.py`](https://github.com/krahets/hello-algo/blob/main/recursion.py) and [`space_complexity.py`](https://github.com/krahets/hello-algo/blob/main/space_complexity.py).
- **Iterative loops** (for/while) achieve **O(1)** constant auxiliary space by avoiding stack frame allocation entirely.
- **Simulated recursion** with explicit stacks maintains **O(n)** space usage but offers manual control over memory layout.
- **Tail recursion** does not optimize to O(1) in CPython due to the lack of tail-call optimization in the interpreter.
- **Recursive data construction** can dominate memory with **O(2ⁿ)** or **O(n²)** allocations, independent of the O(n) call-stack depth.

## Frequently Asked Questions

### Does tail recursion reduce space complexity in Python?

No. According to the hello-algo source code, even the `tail_recur` implementation in [`recursion.py`](https://github.com/krahets/hello-algo/blob/main/recursion.py) consumes O(n) stack space because CPython does not implement tail-call optimization. Each call still generates a new frame until the base case returns.

### Can iterative solutions ever use more space than recursive ones?

Yes, if the iterative algorithm explicitly allocates data structures proportional to input size. However, for the same algorithmic logic—such as summing 1 to n or traversing a linked list—the iterative version in [`iteration.py`](https://github.com/krahets/hello-algo/blob/main/iteration.py) consistently uses O(1) space compared to the O(n) recursive version.

### How does the hello-algo repository demonstrate these differences?

The repository places equivalent implementations in adjacent files like [`recursion.py`](https://github.com/krahets/hello-algo/blob/main/recursion.py), [`iteration.py`](https://github.com/krahets/hello-algo/blob/main/iteration.py), and [`space_complexity.py`](https://github.com/krahets/hello-algo/blob/main/space_complexity.py), allowing direct comparison of `recur` vs. `for_loop` or `linear_recur` vs. iterative alternatives. Each file includes `if __name__ == "__main__":` blocks that execute the functions, demonstrating runtime behavior and memory constraints.

### When should I choose recursion despite the space overhead?

Recursion is preferable when the algorithm naturally follows a recursive data structure (like trees or graphs) or when the recursive logic significantly improves code readability and maintainability. For deep linear recursion (depth > 1000 in Python), iterative approaches or explicit stack simulation are recommended to avoid stack overflow errors.