Module 15 · Recursion and Divide-and-Conquer

141. Factorial with Call Trace

Foundation · Download this solution · All solutions and shared helpers

Problem

Implement factorial recursively for a nonnegative integer n, returning n! and printing one call event and one return event for every invocation. Use 0!=1 and 1!=1. The n=4 example must expose both descent and unwinding; large n is limited by Python recursion depth and integer size.

Examples

Example 1

factorial(4)
=> 24
Printed call/return trace:
call factorial(4)
call factorial(3)
call factorial(2)
call factorial(1)
return factorial(1) = 1
return factorial(2) = 2
return factorial(3) = 6
return factorial(4) = 24

The printed events show four frames and their reverse return order.

Example 2

factorial(0)
=> 1
Printed call/return trace:
call factorial(0)
return factorial(0) = 1

The empty product is the base value one.

Example 3

factorial(1)
=> 1
Printed call/return trace:
call factorial(1)
return factorial(1) = 1

The singleton product is another base case.

Reveal the worked solution and reasoning

Why this mechanism works

A recursive call should promise one complete answer: factorial(n-1) returns the product through n-1. The current call then multiplies that answer by n. Call events occur while descending; return events occur in reverse order as pending multiplications become computable.

State and boundaries

Each frame owns its n and result. The caller waits for one smaller factorial before computing its own result.

Protocol

Print the call event.
Return one for n<=1 after printing its return.
Otherwise obtain factorial(n-1) once.
Multiply by n.
Print and return the completed result.

Visualization

call 4 -> call 3 -> call 2 -> call 1
return 1 <- return 2 <- return 6 <- return 24
work pending on descent completes on unwind

Python implementation

def factorial(n):
    print(f'call factorial({n})')
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1)
    print(f'return factorial({n}) = {result}')
    return result

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

factorial(4)

L2 factorial: print(f'call factorial({n})')
n=4

L2 factorial: print(f'call factorial({n})')
n=3

L2 factorial: print(f'call factorial({n})')
n=2

L2 factorial: print(f'call factorial({n})')
n=1

L4 factorial: result = 1
n=1; result=1

L6 factorial: result = n * factorial(n - 1)
n=2; result=2

L6 factorial: result = n * factorial(n - 1)
n=3; result=6

L6 factorial: result = n * factorial(n - 1)
n=4; result=24

Result: 24. The printed events show four frames and their reverse return order.

factorial(0)

L2 factorial: print(f'call factorial({n})')
n=0

L4 factorial: result = 1
n=0; result=1

Result: 1. The empty product is the base value one.

Why the solution is correct

The base cases match the factorial definition. Assuming the smaller call returns (n-1)!, multiplying by n returns n!, proving correctness by induction. Each recursive argument decreases, so it eventually reaches a base case.

Time and space

O(n) multiplications and O(n) call frames; output integers and arithmetic costs grow with n. Printed trace size is also linear in the number of calls, apart from number lengths.

Common mistakes

Multiplying before the child has returned is not a separate completed result. A missing base case recurses indefinitely until the runtime limit.

Reasoning card

State: Each frame owns its n and result. The caller waits for one smaller factorial before computing its own result.

Invariant: factorial(n) returns the product 1..n.

Decision to rehearse: Separate downward calls from upward combination.

Finish: Print and return the completed result

Transfer exercise

Replace implicit call frames with an explicit stack of pending multipliers, then compare the traces.