4.1.1.15–4.1.1.16 - Stack frames and recursion (Python)

Stack frames

When one subroutine calls another, the caller must retain enough information to continue after that call finishes.

The call stack follows last-in, first-out order. A new call places a new frame on top. When that call returns, its frame is removed and the previous caller resumes. The return address identifies a position in the caller's code; it is different from the returned data value. A language runtime may also save other implementation details, but these three items explain the required model.

Suppose report() is waiting for double(4), and double calls increment(4) twice. The active increment frame stores its parameter 4, its own working values and the point in double to resume. It returns before the next increment invocation begins. This ordinary nesting uses the same stack mechanism as recursion; recursion is not the only reason a program needs frames.

Every recursive invocation receives a separate frame, even when all frames execute the same function definition. Its local n can therefore be 3 while a deeper invocation's n is 2. One invocation does not overwrite the other's local value.

Base and general cases

A recursive solution expresses a problem using a smaller instance of the same problem and a case that needs no further recursive call.

For a non-negative integer $n$, the sum of integers from 1 to $n$ is 0 when $n=0$. Otherwise it is $n$ plus the sum from 1 to $n-1$. Three conditions make this terminate: a reachable base case, progress toward it at each general step, and an input within the function's stated domain.

With input 3, entry messages appear for 3, 2, 1, 0; the base returns 0; leave messages show 1 1, 2 3, 3 6; the answer is 6. Calls descend before pending additions finish. The square-sum modification instead returns 14, with leave results 1, 5, 14. Both versions return 0 for input 0.