Recursion and Call State

Objectives#

• State a base case, a progress measure, and the meaning of one call's return value.
• Trace local variables and shared mutable state across call frames.
• Relate recursion depth to stack space and recognize when an iterative equivalent is safer.
• Distinguish ordinary recursive decomposition from backtracking that explores choices and restores state.

Give one frame a contract#

A useful recursive statement has three parts: what solve(x) returns, which inputs stop immediately, and why every recursive call is closer to stopping. For a subtree sum, sum(node) returns the sum of exactly the nodes reachable below node, and sum(null)=0.

Local variables belong to one active frame. A return value travels to the caller. Shared fields or captured collections outlive a frame, so they need explicit initialization and ownership; otherwise a second invocation can inherit results from the first.

Check the reasoning

• Can you finish the sentence “this call returns…” without referring vaguely to “the answer”?
• Can the progress measure reach the base case on every valid branch?

Find the missing stop and the leaking state#

A traversal that reads node.left before handling null is missing the empty-subtree base case. A class-level total that is not reset before a new traversal is a shared mutable result bug: the recursion may be locally correct while the public operation is not repeatable.

Prefer composing return values when the parent only needs a child's result. Use shared state only when its lifetime and restoration rule are easier to explain than the returned alternative.

Check the reasoning

• What happens on an empty root and on a leaf's null children?
• If the public function runs twice on the same object, which state survives?

Translate frames into an explicit stack#

Recursive depth is the longest active root-to-leaf chain, not the total number of nodes. A balanced n-node tree has O(log n) depth; a one-sided tree has O(n) depth and may exceed the runtime's recursion limit.

An iterative depth-first traversal stores the work that recursive frames would have remembered. Push the root; while the stack is nonempty, pop one node, process it, then push children in the reverse of the desired visit order. The explicit stack still uses O(height) or O(n) space depending on shape, but it avoids call-stack limits.

Check the reasoning

• What data from a suspended call must an explicit stack entry preserve?
• Does child push order match the required traversal order?

Backtracking restores a choice#

Recursion is a control technique: a function calls itself on a smaller or related state. Backtracking is a search discipline: choose, recurse, undo, and try another choice. A recursive tree sum does not backtrack because it does not mutate a partial candidate that must be restored.

Check the reasoning

• Is there a choice tree with sibling alternatives?
• After one branch returns, which mutation must be undone before exploring the next branch?

Worked example: Trace a subtree aggregate#

For root 5 with left child 2 and right child 7, evaluate sum(node) = node.value + sum(node.left) + sum(node.right), with sum(null) = 0.

Conclusion: The base case supplies the empty-subtree identity, each frame returns one complete subtree result, and the iterative form makes the pending frames visible.

Misconception to correct#

If a solution uses recursion, it is backtracking.

Backtracking specifically explores alternatives and restores choice state between siblings. Divide-and-conquer, traversal, and subtree aggregation may be recursive without backtracking.

Short exercise#

A tree counter stores total as an object field and increments it during DFS, but calling count(root) twice returns twice the node count. Name the bug and give two valid repairs.

Put it into practice#

Solve one subtree-return problem, then rewrite the traversal with an explicit stack. Record the return contract, base case, maximum depth, and child push order.