Recursion and Stack Frames

A base case returns a result without another recursive call. The recursive case reduces the problem towards that base case. For non-negative integer factorial, factorial(0)=1 and factorial(n)=n×factorial(n-1) for n>0. The input restriction matters because negative values would not reach zero by repeated subtraction.

A recursive description is not enough by itself: verify that each allowed input eventually reaches a base case and that the returned subproblem result is combined correctly. An incorrectly placed return or unchanged argument can invalidate an otherwise familiar pattern.

Each active call needs its own context, often described using a stack frame. This records information such as parameters, local values and the return address or continuation needed when the call finishes. A new recursive call does not overwrite the older call’s conceptual local state.

When the innermost call returns, its result lets the suspended caller continue. The most recent unfinished call completes first, which is why a stack is appropriate. Implementations may optimise some cases, but the ordinary call-stack model is the required starting point for tracing.

A simple factorial recursion has a number of calls proportional to n and needs proportional call-stack space in the ordinary model. An iterative accumulator can calculate the same result without retaining every unfinished multiplication. Neither style is automatically best for every problem.

Recursive tree traversal can closely match the structure being processed. However, repeated recursive subproblems may multiply work, and very deep recursion may exceed an implementation limit. State both the stopping argument and resource assumptions when comparing an algorithm’s practical suitability.

def factorial(n):
    if n < 0:
        raise ValueError("non-negative input required")
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(4))

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.