4.1.1.15–4.1.1.16 - Stack frames and recursion (C#)

Return addresses, parameters and local state

A caller may need to pause halfway through an expression while another method calculates a result. A stack frame records the information needed for one active call, including the return address, parameters and local variables.

For these two methods, consider the calling statement int result = Double(Increment(3));:

static int Increment(int value) { return value + 1; }
static int Double(int value) { return value * 2; }

First Increment receives 3. Its frame preserves its parameter and a return location in the caller. After it returns 4, that frame is removed. Double is then called with 4, returns 8, and its frame is removed. These calls are not simultaneously waiting inside one another: the inner expression is evaluated before the outer call begins.

For genuinely nested calls, the newest frame sits at the top of the call stack. A call pushes a frame; a completed call pops its frame. This last-in, first-out order ensures that the most recently paused caller resumes first. The stack is a conceptual implementation model; a compiler may optimise details, but each active invocation still needs its own logical state.

In recursion, frames for repeated calls to the same method must remain distinct. If a call with parameter 3 invokes a call with parameter 2, the original 3 must be preserved so it can be used after the smaller call returns. A shared global working variable cannot substitute for these independent values safely.

Base and general cases

Recursion solves a problem by having a subroutine call itself on a smaller or simpler version of the problem. A base case is solved without another recursive call. A general case combines a smaller solution with the current call's contribution.

static int Factorial(int n)
{
    if (n == 0)
    {
        return 1;
    }
    return n * Factorial(n - 1);
}

Assume n is an integer from 0 to 12, so the result fits C#'s int. The base is $0! = 1$. The general rule is $n! = n \times (n-1)!$. Decreasing n by one moves every permitted positive input toward zero. A base case without progress is insufficient: Factorial(n) inside the general case would keep making identical calls. Starting at a negative integer violates this interface and moves away from zero; the method does not claim to handle it.