MyLeoNes™

Recursion — Computing, 14–17 years

How a problem can be solved by making a smaller version of the same problem, with a clear point where the process stops.

Idea

Recursion is when a function solves a task by calling itself on a smaller or simpler input. It must also have a base case: a situation simple enough to answer directly. Each call moves towards that base case, like opening a smaller box inside a box until the last box is reached.

Why it matters

Some problems contain smaller copies of themselves. Folders contain folders, family trees contain branches, and a maze can contain smaller sections to explore. Recursion gives a natural way to describe these shapes, because the same instructions can be reused instead of writing separate code for every possible depth.

Worked example

To calculate 4 factorial, define fact(1)=1 as the base case. Then fact(4)=4×fact(3), fact(3)=3×fact(2), and fact(2)=2×fact(1). Substituting upwards gives 2×1=2, 3×2=6, and 4×6=24, so 4!=24.

Common trap

A reasonable mistake is to write the self-call first and forget the base case or the step towards it. The code then keeps calling itself with no end, because the computer cannot guess when the task is finished. Even with a base case, a wrong step can make the input grow instead of shrink.

Where it appears

Web browsers, file tools and search systems often explore nested folders or linked pages using recursive ideas. Image software can also process a picture by splitting it into smaller regions, then splitting those regions again. Recursion is useful here because the same action applies at every level until a region is small enough.

Keep exploring

Other languages

Loading MyLeoNes™…