A-Level Computer Science 9618 / Topic 19 / A2

It calls itself.

A recursive subroutine solves a problem by calling itself on a smaller version of the same problem until it reaches a case it can answer directly. You write and trace recursive algorithms, follow the call stack as it winds up and unwinds, and judge when recursion is the right tool.

Full-screen labAlgorithms lab → Topic 19All computational thinking and problem-solving lessons →

The key idea

A recursive subroutine is one that is defined in terms of itself: it calls itself. It must have a base case, a condition where it returns a result without calling itself, and a general (recursive) case that calls itself with a value that moves closer to the base case. Each call is placed on the call stack as a stack frame holding its return address, parameters and local variables. When the base case is reached the calls return one by one in reverse order: the stack unwinds. With no reachable base case the stack fills up: stack overflow.

Fig. 1: the call stack for Factorial(4). Five frames are pushed; the base case returns 1 and the frames are popped as the results are multiplied back down.

Section 01

The three features.

Factorial is the classic first example: 4! = 4 × 3 × 2 × 1, and 4! = 4 × 3!. That second form defines the factorial in terms of a smaller factorial, which is exactly what a recursive function does.

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0 THEN
        RETURN 1                         // base case
    ELSE
        RETURN n * Factorial(n - 1)      // general case
    ENDIF
ENDFUNCTION

Calls itself: the function name Factorial appears inside its own definition.
Base case: n = 0 returns 1 without any further call. This is the stopping condition.
General case: n * Factorial(n - 1) calls itself with n reduced by 1, so every call moves towards the base case.
How it is expressed: in a programming language the subroutine simply includes a call to itself, by name, with new arguments. A function returns its value into the expression that called it.

Worked example Trace Factorial(4)

Trace the calls and returns for Factorial(4).

Factorial(4) cannot finish: it needs 4 * Factorial(3), so it calls Factorial(3).
In the same way Factorial(3) calls Factorial(2), which calls Factorial(1), which calls Factorial(0).
Factorial(0) is the base case and returns 1.
Unwinding: Factorial(1) returns 1 * 1 = 1; Factorial(2) returns 2 * 1 = 2; Factorial(3) returns 3 * 2 = 6; Factorial(4) returns 4 * 6 = 24.

Answer:

Call	n	Waits for	Returns
1	4	4 * Factorial(3)	24
2	3	3 * Factorial(2)	6
3	2	2 * Factorial(1)	2
4	1	1 * Factorial(0)	1
5	0	(base case)	1

Five calls in total; the value 24 is returned to the original caller.

Your turn

Power(Base, Exp) returns 1 if Exp = 0, otherwise Base * Power(Base, Exp - 1). How many calls are made by Power(3, 4), and what is returned?

Examiner trap

A base case that is never reached is as bad as none. Factorial(−1) calls Factorial(−2), then −3, ... and never meets n = 0, so the stack overflows. State that each call must move towards the base case.

Section 02

Winding and unwinding.

Where the work happens matters. Anything before the recursive call runs on the way down (winding); anything after it runs on the way back up (unwinding), in reverse order. In the lab, run the in-order, pre-order and post-order traversals of the tree: each is a three-line recursive procedure.

PROCEDURE Mystery(n : INTEGER)
    IF n > 1 THEN
        CALL Mystery(n DIV 2)
    ENDIF
    OUTPUT n MOD 2
ENDPROCEDURE

PROCEDURE InOrder(Node : INTEGER)
    IF Node <> NullPointer THEN
        CALL InOrder(Tree[Node].LeftPointer)
        OUTPUT Tree[Node].Data
        CALL InOrder(Tree[Node].RightPointer)
    ENDIF
ENDPROCEDURE

Mystery: the OUTPUT comes after the call, so nothing is output until the base case (n = 1) is reached. The digits then come out during unwinding.
In-order (left, node, right) visits a binary search tree in ascending order. For the tree 50, 30, 70, 20, 45, 60, 85 it outputs 20, 30, 45, 50, 60, 70, 85.
Pre-order (node, left, right) gives 50, 30, 20, 45, 70, 60, 85; post-order (left, right, node) gives 20, 45, 30, 60, 85, 70, 50. Only the position of the OUTPUT line changes.
Base case of a traversal: a null pointer, an empty subtree, where the procedure does nothing and returns.

Worked example Trace Mystery(13)

State the output of CALL Mystery(13).

Mystery(13): 13 > 1, so call Mystery(6) before any output.
Mystery(6) calls Mystery(3), which calls Mystery(1).
Mystery(1): 1 > 1 is FALSE, so it outputs 1 MOD 2 = 1 and returns.
Unwinding: Mystery(3) outputs 3 MOD 2 = 1; Mystery(6) outputs 6 MOD 2 = 0; Mystery(13) outputs 13 MOD 2 = 1.

Answer: The output is 1, 1, 0, 1: the binary form of 13 (1101). Mystery converts denary to binary

Your turn

A procedure Show(n) does: IF n > 0 THEN OUTPUT n, CALL Show(n - 2), OUTPUT n * 10, ENDIF. What is output by CALL Show(5)?

Examiner trap

In a trace, do not output a value when a call is made if the OUTPUT is after the recursive call. Write each call on a new row, and fill in its output only when control returns to it.

Stage 1 · Learn

Check what the sim just showed you

Four quick checks. Each correct answer earns XP and records this skill on your profile.

Quick check+10 XP

What is the base case in a recursive subroutine?

Quick check+10 XP

What does Factorial(3) return?

Quick check+10 XP

In the lab, which traversal outputs the values of a binary search tree in ascending order?

Quick check+10 XP

Which output does a recursive procedure give for a line placed after its recursive call?

Section 03

What the compiler does.

Recursion only works because each call gets its own copy of its parameters and local variables, and remembers where to return to. The compiler arranges this with a stack, the same LIFO structure you implemented in the last lesson.

On each call: the compiled code pushes a stack frame onto the call stack holding the return address (the instruction to go back to), the parameters and the local variables. The values of the caller are not overwritten.
On each return: the frame is popped, any return value is passed back, and execution continues at the return address with the caller's own variables restored. This is unwinding.
Limits: every frame uses memory. Too many calls before a base case is reached (or no base case at all) fills the stack: a stack overflow error.

Recursion is beneficial when...	Iteration is better when...
the problem is naturally recursive: trees, traversals, divide and conquer (binary search, merge sort), nested structures	a simple loop does the job, as for factorial or summing a list
the recursive version is much shorter and clearer, so easier to write and check	memory is limited: iteration uses O(1) stack space
the depth of recursion is small, so the extra memory is not a problem	speed matters: every call costs time to push and pop a frame

FUNCTION Fib(n : INTEGER) RETURNS INTEGER
    IF n <= 1 THEN
        RETURN n
    ELSE
        RETURN Fib(n - 1) + Fib(n - 2)
    ENDIF
ENDFUNCTION

Worked example Count the calls

How many calls to Fib are made in total when Fib(5) is evaluated?

Fib(0) and Fib(1) are base cases: 1 call each.
Fib(2) = 1 + calls for Fib(1) + calls for Fib(0) = 1 + 1 + 1 = 3. Fib(3) = 1 + 3 + 1 = 5.
Fib(4) = 1 + 5 + 3 = 9. Fib(5) = 1 + 9 + 5 = 15.
Fib(5) returns 5, but Fib(3) is worked out twice and Fib(2) three times.

Answer: 15 calls to return 5. The number of calls roughly doubles each time n rises by 1, so this version is exponential, about O(2ⁿ); a loop keeping the last two values is O(n)

Your turn

Write an iterative version of Factorial, and state one advantage it has over the recursive version.

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    DECLARE Result : INTEGER
    DECLARE i : INTEGER
    Result ← 1
    FOR i ← 1 TO n
        Result ← Result * i
    NEXT i
    RETURN Result
ENDFUNCTION

It uses a fixed amount of memory (no stack frame per step), so it cannot cause a stack overflow, and it avoids the time spent on calls and returns.

Examiner trap

"Recursion is faster" is usually wrong. A recursive solution is often shorter and clearer, but it normally uses more memory and more time than an equivalent loop because of the stack frames.

Stage 2 · Exam

Exam-style questions

Unlocks once the four checks above are done. Worth more XP, written to A Level Paper 3 and Paper 4 standard.

Finish the four checks above to unlock the exam questions

Exam style+20 XP

Which item is NOT stored in a stack frame when a recursive call is made?

Exam style+20 XP

A recursive function has no reachable base case. What happens when it runs?

Exam style+20 XP

Mystery(n) calls Mystery(n DIV 2) when n > 1, then outputs n MOD 2. What does CALL Mystery(10) output?

Exam style+20 XP

When is recursion most likely to be the better choice than iteration?

Skill unlocked

Recursion, mastered.

This skill is now recorded on your profile. Keep the chain going.

-Rank -Level -Score -Topics

Go deeper · practice

Six original Cambridge-style questions

Writing and tracing recursive algorithms, the call stack and unwinding, and when recursion is beneficial.