Recursion

Computer Science A2 · Computational thinking and Problem-solving. The idea in plain words, the rules to remember, the mistake to avoid and a worked example, written and checked by Mega Lecture.

Test this topic free All Computer Science A2 topics

The idea

A recursive routine is one that calls itself. It must have a base case, a condition where it gives an answer without calling itself, and a general case that calls itself with a value that moves towards the base case. Without these it never stops.

Each call is put on the call stack with its own parameters, local variables and return address. When the base case is reached the calls finish in reverse order and pass their results back. This is called unwinding.

Recursion gives short, clear code for problems that are naturally recursive, such as tree traversal or factorial. It uses more memory than a loop, and very deep recursion can cause stack overflow.

Rules to remember

Essential features: a base case, a general (recursive) case, and each call moving closer to the base case.
Each call pushes a stack frame holding its parameters, local variables and return address.
On return the frame is popped and control goes back to the statement after the call (unwinding).
To trace: write the calls down the page until the base case, then work the return values back up.
Statements placed after the recursive call run during unwinding, so their output appears in reverse order.
No base case, or a base case that is never reached, gives endless calls and stack overflow.
Any recursive routine can be rewritten with a loop; the loop usually runs faster and uses less memory.

Common mistake

Students stop the trace at the base case and give its value as the answer. The base case value must be passed back through every waiting call before the first call can return.

Worked example

FUNCTION Power(B, E) returns 1 if E = 0, otherwise it returns B * Power(B, E − 1). What does Power(3, 4) return, and how many calls are made in total?

Winding: Power(3, 4) calls Power(3, 3), then Power(3, 2), Power(3, 1) and Power(3, 0).
Power(3, 0) is the base case and returns 1. That is 5 calls altogether.
Unwinding: 3 × 1 = 3, then 3 × 3 = 9, then 3 × 9 = 27, then 3 × 27 = 81.

Answer: It returns 81 after 5 calls (5 stack frames at the deepest point).

Ask about this

Type what you are stuck on. The helper finds the explanation, worked examples and the notes to read, free and instant.

Keep going

← Algorithms Programming Paradigms →Take a Computer Science A2 test