Recursion and the Call Stack

Recursion is a way to solve a problem by defining it in terms of a smaller version of itself. In Python, this means a function calls itself.

The syllabus expects you to understand recursion, trace recursive and non-recursive programs, and understand the use of stacks in recursive programming.

The Two Required Parts

A recursive function needs:

• a base case: the case that stops recursion;
• a recursive case: the case that calls the same function with a smaller or simpler input.

Without a reachable base case, the function keeps calling itself until Python raises an error.

Countdown Example

def countdown(n):
    if n == 0:
        print("Done")
    else:
        print(n)
        countdown(n - 1)

For countdown(3), the output is:

3
2
1
Done

The base case is n == 0. The recursive case prints n and calls countdown(n - 1).

Order Matters

If the recursive call happens before the print(), the output changes.

Caption: Recursive calls move toward the base case; returned values then resolve the waiting expressions in reverse order.

def countup(n):
    if n == 0:
        print("Done")
    else:
        countup(n - 1)
        print(n)

For countup(3), the output is:

Done
1
2
3

The calls go down to the base case first. Then the waiting calls continue in reverse order.

This is the main beginner trap in recursion: the line after the recursive call does not run immediately. It waits until the smaller call has finished.

Tracing Calls and Returns

A complete recursive trace has two phases:

1. Call phase: each call records its local values and waits for the smaller call.
2. Return phase: the base case finishes, then waiting calls resume in last-in, first-out order.

For written traces, record both phases. A table that lists only the downward calls may miss output or calculations that occur after the recursive call.

Recursive Return Values

Some recursive functions return values.

def factorial(n):
    # Assumes n is a positive integer.
    if n == 1:
        return 1
    return n * factorial(n - 1)

Trace for factorial(4):

Call	What it needs	Return value
factorial(4)	4 * factorial(3)	24
factorial(3)	3 * factorial(2)	6
factorial(2)	2 * factorial(1)	2
factorial(1)	base case	1

The final answer is built as the calls return:

factorial(1) returns 1
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24

Stack Frames and Return Addresses

A stack frame stores the information needed for one active function call, including its local variables and where execution should continue when the called function returns.

The Call Stack

When a function is called, Python keeps information about that call in a stack frame. The frame includes local values and the point where execution should resume after the call returns.

Caption: Each recursive call pushes a stack frame containing its local state and waiting work; frames pop in reverse order as values return.

The stack follows last-in, first-out order. When a recursive call is made, a new frame is pushed. When that call returns, its frame is popped:

• the most recent call is completed first;
• earlier calls wait underneath it;
• each return removes one frame from the stack.

Recursive Versus Iterative Thinking

Iterative factorial:

def factorial_iterative(n):
    # Assumes n is a positive integer.
    result = 1
    while n > 1:
        result = result * n
        n = n - 1
    return result

Recursive factorial:

def factorial_recursive(n):
    # Assumes n is a positive integer.
    if n == 1:
        return 1
    return n * factorial_recursive(n - 1)

Both can compute the same value. The iterative version updates variables inside a loop. The recursive version relies on smaller function calls and the call stack.

Choosing a Valid Base Case

The base case must match the allowed input domain. The earlier factorial version assumes a positive integer. A version that accepts zero should use $0!=1$:

def factorial(n):
    # Assumes n is a non-negative integer.
    if n == 0:
        return 1
    return n * factorial(n - 1)

For invalid negative input, the recursive argument moves farther from the base case. In practical code, validate the input before recursion.

Benefits and Drawbacks

Recursion can be elegant when a problem naturally has smaller subproblems, such as tree traversal or processing a nested structure. It can also be easier to reason about once the base case and recursive case are clear.

Drawbacks:

• each call uses stack memory;
• too many calls may exceed the recursion limit;
• a missing or wrong base case causes non-termination;
• some recursive solutions are less efficient than iterative ones.

Common Bugs

• No base case.
• Base case exists but is never reached.
• Recursive call does not make the problem smaller.
• Returning a value in the base case but forgetting to return in the recursive case.
• Printing during recursion when the question asks for a returned value.
• Confusing call order with return order.

Practice Trace

Trace:

def mystery(n):
    if n == 1:
        return 1
    return mystery(n - 1) + n

For mystery(4):

mystery(1) = 1
mystery(2) = 1 + 2 = 3
mystery(3) = 3 + 3 = 6
mystery(4) = 6 + 4 = 10

This computes the sum from 1 to n.

Check Your Understanding

Try these before looking back at the explanations:

1. What two parts must every correct recursive solution have?
2. Why does countup(3) print 1 only after Done?
3. What happens to a stack frame when a function returns?
4. In factorial(4), which call reaches the base case first?

Answers:

1. A base case and a recursive case.
2. The recursive calls reach the base case before the waiting print(n) statements resume.
3. It is removed from the call stack.
4. factorial(1).

Related Notes

• Programming Fundamentals
• Control Flow and Functions