# Recursion and the Call Stack — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/s-stack

> Account for stack space in recursive algorithms.

## Every pending call uses memory

Recursive calls are not free in memory. Each active call keeps a **stack frame** with its parameters, local variables and return address until it returns. The space used by the stack is proportional to the **maximum recursion depth**, not the total number of calls. Summing a list recursively goes n calls deep, so it uses **O(n)** stack space even though it allocates no data structures. Binary search recursion goes about log₂ n deep, so **O(log n)** space; an iterative binary search uses O(1). Merge sort's recursion depth is O(log n), but its merging uses O(n) auxiliary arrays, so its total auxiliary space is **O(n)**. Quicksort uses O(log n) stack space on average but O(n) in the worst case, unless it always recurses on the smaller part first. Deep recursion can also crash programs: Python's default recursion limit is about 1,000 frames and it does not optimise **tail calls**, and other languages hit stack overflow errors on very deep recursion. Convert deep recursion to iteration with an explicit stack when inputs can be large.

## Stack space in recursive and iterative versions

Depth, not call count, determines stack space.

```python
def depth_sum(a, i=0):
    if i == len(a):
        return 0
    return a[i] + depth_sum(a, i + 1)     # n frames at once -> O(n) stack space
                                           # for n > ~1000, Python raises RecursionError

def iter_sum(a):
    s = 0
    for x in a:                            # O(1) extra space
        s += x
    return s

def dfs_iterative(graph, start):
    stack, seen = [start], {start}         # explicit stack instead of recursion
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                stack.append(nxt)
    return seen                            # O(V) space for seen and stack
```

## A stack of unfinished tasks

Each recursive call is like putting a half-done task on a pile while you start a smaller one. The height of the pile at its tallest, not the total number of tasks you ever touched, decides how much desk space you need.

**Quiz:** What is the stack space used by a recursive function that recurses on n − 1 until reaching 0?

- [ ] O(1)
- [ ] O(log n)
- [ ] O(n²)
- [x] O(n)

*Answer:* O(n). The recursion is n levels deep, so n frames exist at the deepest point.