What is not reducing the input?

Calling the function on the same or a larger input never reaches the base case; the argument must shrink each call.

SingaporeComputer ScienceSyllabus dot point

How does a function that calls itself solve a problem, and when is recursion the right tool?

Define recursion in terms of base and recursive cases, trace recursive calls, and compare recursion with iteration

A focused answer to the H2 Computing outcome on recursion. Base and recursive cases, tracing the call stack, the divide-and-conquer pattern, and the trade-offs between recursion and iteration.

Generated by Claude Opus 4.88 min answerUpdated 2026-06-06

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

SEAB wants you to define recursion through its base and recursive cases, trace recursive calls including how the call stack unwinds, and weigh recursion against iteration. The central idea is that a recursive function solves a problem by reducing it to a smaller version of the same problem, stopping when it reaches a base case simple enough to answer directly.

The answer

The two parts of every recursion

A correct recursive function has:

a base case - a condition that returns an answer without recursing, stopping the process, and
a recursive case - which calls the function on a smaller input, moving toward the base case.

def countdown(n):
    if n == 0:           # base case
        print("done")
        return
    print(n)
    countdown(n - 1)     # recursive case, smaller input

Without a reachable base case, the function recurses forever and the call stack grows until a stack overflow crashes the program.

The call stack

Each call is pushed onto the call stack, holding its own parameters and local variables. When a call reaches the base case it returns, and the stack unwinds, each waiting call completing with the returned value. Tracing recursion means writing out the calls going down, then the returns coming back up.

Divide and conquer

Recursion underlies the divide-and-conquer pattern: split a problem into smaller subproblems, solve each recursively, and combine the results. Merge sort, quicksort and binary search are all expressed this way - each recurses on a smaller portion of the data.

Recursion versus iteration

Any recursion can be rewritten as a loop (iteration), and vice versa:

Recursion is clearer for self-similar problems (trees, divide and conquer) and often shorter.
Iteration uses no extra stack frames, so it avoids call overhead and stack-overflow risk, and is usually faster for simple repetition.

Choose recursion when the problem is naturally recursive; choose iteration for straightforward repeated steps.

Worked example

Trace sum_to(3), which returns the sum $1 + 2 + 3$ , and show the call stack unwinding.

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

Step 1: Descend through the recursive calls

sum_to(3) = 3 + sum_to(2)
sum_to(2) = 2 + sum_to(1)
sum_to(1) = 1 + sum_to(0)
sum_to(0) = 0           (base case, returns)

Step 2: The base case returns

sum_to(0) returns $0$ without recursing, so the stack stops growing.

Step 3: Unwind, substituting each return

sum_to(1) = 1 + 0 = 1; then sum_to(2) = 2 + 1 = 3; then sum_to(3) = 3 + 3 = 6.

Step 4: State the result

sum_to(3) returns $6$ , the sum $1 + 2 + 3$ . The four calls were pushed in order and returned in reverse order as the stack unwound.

Examples in context

Example 1. Navigating folders. Listing every file in a directory and its subdirectories is naturally recursive: process the files here, then recurse into each subfolder. The folder tree is self-similar, so the recursive solution mirrors the structure far more cleanly than a manual loop with an explicit stack.

Example 2. Evaluating nested expressions. A calculator parsing 2 * (3 + (4 - 1)) recurses into each bracketed subexpression, evaluating the innermost first as the base case. The nesting of brackets is exactly the nesting of recursive calls, which is why language interpreters lean on recursion.

Try this

Q1. State what every recursive function must contain to avoid infinite recursion. [1 mark]

Cue. A base case that returns without recursing, which the recursive case must move toward.

Q2. What happens if a recursive function never reaches its base case? [1 mark]

Cue. It recurses forever, growing the call stack until a stack overflow crashes the program.

Q3. Give one reason to prefer iteration over recursion for a simple repeated calculation. [2 marks]

Cue. Iteration uses no extra stack frames, avoiding call overhead and stack-overflow risk, and is usually faster for plain repetition.

Exam-style practice questions

Practice questions written in the style of SEAB exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Original6 marksConsider this recursive function. Identify the base case and the recursive case, and trace the call sequence and return values for `factorial(4)`.

Show worked answer →

The function:

def factorial(n):
    if n <= 1:
        return 1            # base case
    return n * factorial(n - 1)   # recursive case

The base case is n <= 1, returning 1 - this stops the recursion. The recursive case is n * factorial(n - 1), which reduces the problem toward the base case.

Trace of factorial(4):

factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1                 (base case)

Unwinding the returns: $1 \\to 2 \\times 1 = 2 \\to 3 \\times 2 = 6 \\to 4 \\times 6 = 24$ . So factorial(4) returns $24$ .

Markers reward identifying both cases, the descending calls to the base case, and the correct unwinding to $24$ .

Original5 marks(a) State the two parts every correct recursive function must have, and what happens if the base case is missing. (b) Give one advantage and one disadvantage of recursion compared with iteration. (c) Name a problem for which a recursive solution is especially natural.

Show worked answer →

(a) Every recursive function needs a base case (a condition that returns without recursing) and a recursive case (which calls itself on a smaller problem moving toward the base case). If the base case is missing or never reached, the function recurses forever, growing the call stack until a stack overflow crashes the program.

(b) Advantage: recursion can express naturally self-similar problems (trees, divide and conquer) far more clearly and concisely than iteration. Disadvantage: each call uses stack space and has call overhead, so recursion can use more memory and be slower, and risks stack overflow on deep recursion.

(c) Traversing a tree, or computing factorials, Fibonacci numbers, or merge sort - any problem defined in terms of smaller instances of itself.

Markers reward both required parts with the infinite-recursion consequence, a genuine advantage/disadvantage pair, and a naturally recursive problem such as tree traversal.