Stack vs. Heap
18 min
Most languages split memory into (at least) two regions with very different behavior. The stack holds each function call's local variables and return address as a frame, pushed on call and popped on return — fast, automatic, but FIXED SIZE, which is exactly why deep or infinite recursion crashes with a stack overflow. The heap holds dynamically-allocated data that can outlive the function that created it (an object returned from a function, a growable list) — flexible, but slower to allocate and (in languages without a garbage collector) manually managed.
def simulate_call_stack(calls, max_depth):
stack = []
for event in calls:
if event[0] == "call":
stack.append(event[1])
if len(stack) > max_depth:
return "stack overflow"
elif event[0] == "return":
stack.pop()
return "ok"
Python actually enforces this exact same idea via sys.getrecursionlimit() (default 1000) -- it deliberately crashes a runaway-recursive function with a RecursionError well before the OS's real, much larger call stack would actually overflow and crash the whole interpreter.
Write `simulate_call_stack(calls, max_depth)`: `calls` is a list of `('call', fn_name)` or `('return',)` events. Maintain a stack of active calls; if a `'call'` ever pushes the stack past `max_depth`, immediately return `'stack overflow'`. If every event processes without exceeding `max_depth`, return `'ok'`.
Why does unbounded RECURSION (a function that keeps calling itself with no base case) crash with a 'stack overflow' specifically, rather than just running forever?
You can simulate a bounded call stack and detect a stack overflow, and understand why unbounded recursion specifically crashes this way (a fixed-size stack, not an unbounded heap).