Recursion — Computing, 11–13
Recursion solves a large problem by applying the same rule to a smaller version of the problem, until a simple stopping point is reached.
A rule that calls itself
In recursion, an instruction deals with one piece and then asks the same instruction to deal with a smaller piece. It must also know when to stop, called the base case. A picture of a branch can show the idea: each branch splits into smaller branches, but the smallest twig does not split again.
Why use recursion?
Some things are made from smaller copies of the same kind of thing: folders contain folders, family trees split into branches, and maps contain regions inside regions. A long list of separate instructions would be hard to write and change. Recursion came from the problem of describing these nested structures with one clear rule instead of repeating similar code.
Counting down
Use a rule called count(n): if n is 0, stop; otherwise print n and call count(n−1). Start with count(3). It prints 3, then calls count(2), which prints 2 and calls count(1). That prints 1 and calls count(0); the base case stops, so the final output is 3, 2, 1.
Forgetting the stop
A recursive rule can look elegant, so it is tempting to let it call itself without checking a base case. That is a reasonable mistake: the smaller tasks seem as if they will eventually run out. Without a stop, however, the value may never reach the answer, and the computer keeps creating unfinished calls until it runs out of space or reports an error.
Folders and branching shapes
File browsers can search a folder, then each folder inside it, no matter how deeply folders are nested. Drawing programs also use recursion for branching plants, snowflake-like shapes and maze paths. You do not need recursion for every repeated action; it is most useful when each part contains smaller parts with the same structure.
Keep exploring
Other languages
Loading MyLeoNes™…