Recursion and the call stack — every question, written out
Frames, depth, tail calls and the conversion to iteration — plus what actually overflows and when.
A function calls itself. What happens to the caller’s local variables while the inner call runs?
Trace prediction
They stay in the caller’s own frame, untouched, and resume when the inner call returns
Calling a function allocates a frame holding its parameters, its locals, and a bookmark for where in the function it currently sits. The caller’s frame stays exactly as it was while the new frame goes on top, and a return tears down the top frame so the one beneath resumes at its bookmark with locals intact. Sixteen nested calls are sixteen bookmarks, each waiting its turn.
See it run — Three frames stacked — visit(A), visit(B), visit(C) — each holding its own node, none overwriting another.
Merge sort on 16 elements makes 31 calls in total. How many frames are on the stack at once?
Complexity derivation
At most five — a finished call is torn down before its sibling starts, so only the depth counts
Depth and call count are different quantities, and only depth is memory. Merge sort makes 2n−1 calls on n elements — 31 here — yet a range’s left half is entirely finished and popped before the right half begins, so the stack never exceeds log₂ 16 + 1 = 5 frames. That is why merge sort’s stack cost is O(log n) despite a linear number of calls.
See it run — The deepest frame of the entire run: sort(0..0) at depth 4, which is five frames counting the root.
Quicksort’s stack is usually quoted as O(log n). What drives it to O(n), and how bad does it actually get?
Complexity derivation
Repeated extreme pivots — on 16 equal keys the recorded run reaches depth 15 instead of depth 4
Stack depth is the depth of the recursion tree, which is decided by how evenly each pivot splits its range. An extreme pivot leaves n−1 elements on one side, so the chain becomes n links long instead of log n. The traces make the gap concrete: the same 16-element array reaches depth 4 when sorted and depth 15 when every key is equal.
See it run — sort(15..15) is pushed at depth 15 — a 16-element array holding sixteen frames at once.
So how do production quicksorts keep the stack from ever reaching O(n)?
Trade-off & selection
Recurse into the smaller side and loop on the larger one, which bounds the depth at log n
The smaller side of a partition holds at most half the range, so recursing into it and iterating on the other caps the depth at log₂ n even when the splits are terrible. The larger side is handled by updating the loop bounds rather than making a call — the tail position that most runtimes will not eliminate for you. Introsort adds a second guard: past a depth threshold it switches to heap sort, turning the quadratic worst case into n log n.
A recursive DFS over a path-shaped graph of 100,000 nodes crashes. What ran out, and why that?
Edge case reasoning
The call stack — one frame per node along the path, and the stack is only a few megabytes
The stack is small — a few megabytes, roughly 10⁴ to 10⁵ frames depending on the runtime, and Python refuses at about 1,000 by default. A path-shaped graph makes DFS descend once per node, so the depth equals the node count and the limit arrives long before the heap is troubled. The fix is an explicit stack: the same pending work relocated to the heap, where there is room for it.
Which line computes a subtree’s height — the one before the recursive calls, or the one after?
Invariant identification
After — the children’s answers do not exist until their frames have finished and returned
Code before the recursive call runs on the way down; code after it runs on the way back up, once everything deeper has fully finished. Height is one plus the maximum of the children’s heights, so it belongs in the after-the-call slot where those numbers exist. The same distinction organises the whole traversal family: emit before for pre-order, after for post-order, between the two calls for in-order.
Your recursion is tail recursive. Is deep recursion safe now?
Comparison
Only in a runtime that eliminates tail calls — Python never does, and JavaScript engines effectively do not
Tail-call elimination means the compiler reuses the current frame when the recursive call is the very last act, turning the recursion into a loop. It is real in Scheme and some functional languages, and absent or unreliable where most interviews live. So “it is tail recursive” describes the shape of the code, not a safety guarantee — if depth is the risk, write the loop yourself.
You convert a recursive DFS into an iterative loop with an explicit stack. What has actually changed?
Trade-off & selection
The pending work moved from the call stack to the much larger heap — the amount of state is the same
Recursion depth is memory, so converting to an explicit stack relocates that memory rather than eliminating it — the win is that the heap holds millions of entries where the call stack holds thousands. The transformation is mechanical for DFS-shaped code and fiddly for in-order traversal, where the “left spine pending” discipline has to be maintained by hand. Expect the visit order to differ unless the children are pushed in reverse.
A backtracking solver returns boards containing pieces left over from abandoned branches. Where is the bug?
Code diagnosis
State mutated on the way down is never undone on the way back up, so siblings inherit the leftovers
Anything changed before the recursive call must be changed back in the after-the-call slot, or the next sibling branch begins from a board the previous branch dirtied. That one rule is the entire bug surface of backtracking, which is why N-Queens treats backtracks as a first-class event rather than hiding them. When undoing is awkward, the alternative is to pass a fresh copy down and pay the memory instead.
What must every recursive call guarantee for the recursion to be well founded?
Invariant identification
Strict progress toward a base case — a smaller range, a shorter list, one more cell fixed
A call that can recurse on a problem the same size as its own is an infinite descent with a crash at the end. Progress is what makes the induction sound: every chain of calls has to reach a base case in finitely many steps. Write the base case first, then make each recursive call on something strictly smaller, and correctness follows almost mechanically.
Pause a recursive DFS midway through. What do the frames on the stack spell out?
Invariant identification
The path from the start node to the node being explored, one frame for each node on it
Every frame is a call that has entered a node and not yet finished it, and each was pushed by the frame below, so the chain of frames is exactly the chain of edges from the start. The frames are not a metaphor for the path — they are the path, which is why the call-frame panel and the highlighted route always agree. It is also why the depth of the search and the length of the current path are one number.
See it run — Five frames — A, B, D, G, L — with the invariant panel naming the active path as the call stack.
Asked for the space complexity of a recursive DFS over a graph, what is the complete answer?
Complexity derivation
O(V) — one mark per node in the visited set, plus a recursion depth that reaches V in the worst case
Both terms are O(V), and giving both unprompted is the tell that you hold the frame model rather than a memorised number. The visited set is one mark per node, and the recursion is one frame per node on the current path, which reaches every node when the graph is one long path. If the depth is the risk, the iterative version moves the same state onto the heap.
Memoizing fib(n) removes the exponential number of calls. Does it remove the stack-overflow risk?
Edge case reasoning
No — the first descent still goes n frames deep before a single value is returned
Memoization fixes how many distinct computations happen and leaves the shape of the first descent untouched: fib(n) calls fib(n−1) calls fib(n−2), all the way down, before any answer comes back. The depth is therefore still n, which is why the bottom-up loop is the version that ships for large n. In the recorded run of fib(7) the leftmost spine reaches fib(1) before a single value is stored.
See it run — The first descent has reached f(1) with every ancestor still open — the cache has returned nothing yet.
Recursive operations are safe on an AVL tree and risky on a plain BST. What makes the difference?
Trade-off & selection
Balancing bounds the height at about log n, so the data’s shape bounds the recursion depth
A plain BST built from sorted insertions degenerates into a linked list, so its recursion depth is n and the stack limit becomes a real ceiling. Rotations keep an AVL tree’s height within a constant factor of log n, which caps the depth of every recursive descent. Sometimes fixing the data is easier than fixing the code, and this is the clearest example of it.
Gathering results by returning a list upward, versus passing one accumulator down — what is the difference?
Comparison
Returning allocates and concatenates at every level; an accumulator appends once per element into one list
Returning a fresh list from every call reads cleanly and can be quadratic, because each level copies all of the results beneath it. Threading a single accumulator through the calls makes each element cost one append, which is the standard fix for traversals that gather output. It is the same reasoning that makes string building in a loop use a buffer instead of repeated concatenation.
A candidate converts recursive DFS into an iterative loop, but uses a queue for the pending nodes. What happens?
Code diagnosis
It becomes BFS — a correct traversal, but one that sweeps in rings instead of following a branch down
The pending-work container is what separates the two traversals: last-in-first-out follows one branch to its end, first-in-first-out sweeps outward level by level. Swapping the structure silently swaps the algorithm, which stays correct as a traversal and breaks whatever depended on the order. It is also the cheapest way to remember the pair — DFS is a stack, BFS is a queue, and the loop around them is the same.
Explain recursion, and why it never loses track of where it was, to someone learning to program. Say it out loud before revealing.
Explain it plainly
When you call a function, the computer sets aside a little slip of paper for that call: its inputs, its own variables, and a bookmark saying which line it is on. If that function calls something else — including itself — your slip stays exactly where it is, and a brand new slip goes on top of the pile. So sixteen nested calls are sixteen slips, each one paused at its own bookmark, and when the top one finishes it is thrown away and the one underneath picks up precisely where it left off with everything it had. That is the whole trick: recursion does not remember anything magically, it just leaves a pile of paused work behind it. Two practical consequences I would add. The code you write before the recursive call happens on the way down, and the code after it happens on the way back up, once everything deeper has finished — which is why “the height of a tree is one plus the taller child” has to go after the call. And the pile is not free: it lives in a small area of memory, usually a few megabytes, so a recursion that goes a hundred thousand levels deep crashes even though the logic is perfectly correct. When that is a risk, you keep the same pending work in a stack you manage yourself, on the heap, where there is far more room.
A strong answer describes frames without jargon, names the two moments a call has, and volunteers the cost — depth is memory, and the stack is small. The tell is whether the listener could predict what happens when the recursion goes too deep.