Recursion and the Call Stack

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.

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.

त्वरित जाँच: 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²)
• O(n)