Recursion, Base Cases and Call Traces

Ontario Grade 12 Computer Science

Programming Concepts and Skills

Follow calls down and values back up

Recursion solves a problem by asking the same function to solve a smaller version. A correct recursive algorithm needs a base case that does not recurse and a step that gets closer to that case. Factorial is a small, useful tracing example: factorial of 3 means 3 × 2 × 1. We use non-negative whole-number inputs only. The displayed Python 3 function has a base case at zero and decreases n by one at each call. The diagram shows the call chain, while the table shows returned values in the opposite direction.

What you will learn

Identify the base case.
Order recursive calls and returned values.
Explain why the example terminates.

Set a clear precondition

The argument n must be a non-negative integer. For n = 3, each call uses a smaller integer: 3, then 2, then 1, then 0. If the function accepted a negative n without a guard, subtracting one would move farther from zero forever. This short lesson traces only valid inputs and does not claim the code checks every invalid case.

Follow calls downward

factorial(3) cannot return yet; it needs factorial(2). That call needs factorial(1), which needs factorial(0). At n = 0 the first branch returns 1 without another call. This is the reachable base case. The tree diagram has one path because each call creates exactly one further call for this input. Its arrows represent calls, not multiplication results.

Follow results upward

After factorial(0) returns 1, factorial(1) returns 1 × 1 = 1. Then factorial(2) returns 2 × 1 = 2. Finally factorial(3) returns 3 × 2 = 6. The order of return is the reverse of the call order. A trace table makes that distinction explicit; skipping straight from the initial call to six can hide a missing base case or a mistaken multiplication.

Return trace

Call	Calculation	Returned value
factorial(0)	base case	1
factorial(1)	1 × 1	1
factorial(2)	2 × 1	2
factorial(3)	3 × 2	6

Worked example

Trace factorial of three

Read the Python 3 function. Which calls occur, and what value should the final print show?

Call chain for factorial(3)

Each arrow means that the parent call asks the next call to solve a smaller input. Returns travel upward in the opposite direction.

Python 3

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(3))

Descend toward the base case
Calls use n = 3, 2, 1 and 0 in that order.
Return from zero
factorial(0) returns 1 without another call.
Unwind
The remaining calls return 1, 2 and then 6.

Answer: Expected output: 6. Call order: 3 → 2 → 1 → 0; return values: 1 → 1 → 2 → 6.

Check: The function is traced rather than executed here; n decreases to the base case for non-negative integer inputs.

Common mistakes and how to avoid them

Omitting a reachable base case, or using factorial(n + 1) instead of factorial(n - 1).

Correction: For non-negative n, stop at n = 0 and reduce n by one in each recursive step.

Lesson summary

A base case returns without recursing.
The argument must progress toward that case.
Return values travel back through calls in reverse order.

Check your understanding

Question 1

What does factorial(0) return in this function?

0
1
3
It calls itself

Show answer and explanation

1

The base-case branch returns 1.

Question 2

What is the last value returned for factorial(3)?

1
2
3
6

Show answer and explanation

6

After unwinding, 3 × 2 = 6.

Key terms

Base case: The input case answered without another recursive call.
Unwind: Return through pending calls after the base case is reached.

Continue through ICS4U

View the complete ICS4U Ontario Grade 12 Computer Science curriculum and lessons

About this lesson and its review

Published by DoAssignment. This reviewed lesson follows Ontario Grade 12 Computer Science (ICS4U), expectation A3.6. It is a study resource, not an official curriculum publication.

Before publication, content is checked for structure, mathematical or chemical notation, calculations, course boundaries, and readability. Errors can still occur, so corrections are welcomed.

Official curriculum reference

Report a correction or ask a question

A3.6 · Recursion, Base Cases and Call Traces