Recursion (Years 10–11) — Computer Science

A function that calls itself, using a base case to stop and a recursive case that shrinks the problem, with calls building up and unwinding on the call stack.

Open a Russian doll and you find a smaller doll inside. Open that one, and there is another, smaller still — until at last you reach a tiny doll that will not open. You have just performed a recursion: the same action repeated on a smaller version of itself, stopping only when you hit the one that cannot go further. In computing, a recursive function is a function that solves a problem by calling itself on a smaller piece of that problem.

Why this matters: Some problems are naturally "self-similar" — searching folders inside folders, or breaking a big task into identical smaller tasks. Recursion lets you describe these in a few tidy lines. It also underpins clever algorithms like merge sort and binary search, so examiners love it.

A recursive call: each box calls a smaller copy of itself.

Two parts every recursion needs

A recursive function always has two pieces. The base case is the simplest problem, which can be answered directly with no more calls — it is the tiny doll that will not open. The recursive case calls the function again on a smaller input, marching steadily towards the base case.

The base case stops the shrinking: when it is reached, calls stop.

The call stack builds up, then unwinds

When a function calls itself, the computer pauses the outer call and remembers it on the call stack — like stacking plates. Calls pile up until the base case is met; then each call returns its answer and the stack unwinds back down, plate by plate.

3! builds up as 3×fact(2)… then unwinds to give 6.

Take factorial: 3! means 3×2×1 = 6. In recursion, fact(3) = 3 × fact(2), fact(2) = 2 × fact(1), fact(1) = 1 × fact(0), and fact(0) = 1 is the base case. As the stack unwinds, the multiplications finish: 1, then 2, then 6.

	Recursion	Iteration (loop)
How it repeats	Function calls itself	A loop repeats a block
Stopping	Base case	Loop condition
Memory	Uses the call stack	Very little extra
Reads well for	Self-similar problems	Simple counting

Recursion (self-calling) versus a loop that repeats a block.

Worked reasoning: Trace countdown(3), which prints n then calls countdown(n−1), with base case n = 0 (do nothing). Prints 3, calls countdown(2) → prints 2, calls countdown(1) → prints 1, calls countdown(0) → base case, stops. Output: 3, 2, 1. Three recursive calls, then the stack unwinds.

Common mistake: Forgetting the base case, or writing a recursive case that never gets smaller. Then the function calls itself forever, the call stack keeps growing, and the program crashes with a stack overflow. Always check: does every path shrink towards the base case?

Memory hook: Every recursion needs a Base case to stop and a Recursive case that shrinks — "Base + smaller Self". No base case = infinite recursion = crash.