Recursion

Stand between two mirrors: you see your reflection, and inside it your reflection again, and inside that one more, seemingly forever. Or look at a fern leaf: every branch looks like a small fern leaf, and its branches do too. This pattern, where something contains a smaller version of itself, is called recursion. In computer science it is one of the most powerful tools there is.

A function calls itself

You know functions as machines: something goes in, something comes out. The trick of recursion: a function may call itself, with a smaller input. A countdown shows this perfectly: countdown(3) says 3 and then calls countdown(2). That one says 2 and calls countdown(1). That one says 1 and calls countdown(0). Each call handles one small piece and passes the rest on to itself.

The base case stops the chain

What happens at countdown(0)? Here the function has to say: stop, I am done, and NOT call itself again. This exit is called the base case. Without it the chain would never end, like the mirrors in the mirror: new calls forever, until the computer runs out of memory and the program crashes. Every recursive function therefore needs two things: a base case to stop, and a step that makes the problem smaller.

Factorial: recursion that calculates

Recursion can also calculate. The factorial of a number multiplies all numbers from 1 up to it: factorial(4) is 4 times 3 times 2 times 1, which is 24. Thought of recursively: factorial(4) is simply 4 times factorial(3). And factorial(3) is 3 times factorial(2), and so on, until the base case factorial(1) = 1 stops the chain. Then the results flow back: 1, then 2, then 6, then 24. One big problem, solved by many small copies of itself.