Recursion

Have you ever seen a set of Russian nesting dolls? You open the big doll and find a smaller one inside, open that and find a smaller one still — until finally you reach a tiny doll that doesn't open at all. Recursion is exactly this idea in code: a function that solves a big problem by calling itself on a smaller version of the same problem, again and again, until it reaches a case so small the answer is obvious.

A function that calls itself is called a recursive function. Every one you will ever write has the same two ingredients:

Miss either ingredient and recursion falls apart — as we'll see.

Your first recursion: a countdown

Here is a rocket countdown. To count down from n, print n, then count down from n - 1 — which is the same job, one step smaller. The base case is reaching 0: there's nothing left to count, so we launch. Press Run and watch it work.

function countdown(n: number): void { if (n === 0) { // base case: nothing left to count console.log("Lift-off! 🚀"); return; } console.log(n); // do a little work... countdown(n - 1); // ...then recurse on a smaller problem } countdown(5);

Notice there is no loop anywhere — yet it repeats. Each call handles one number and hands the rest to another call of the very same function.

A classic: factorial

The factorial of a whole number (written n!) is every number from 1 up to n multiplied together — so 4! = 4 \times 3 \times 2 \times 1 = 24. It has a beautifully recursive definition, because n! is just n times the factorial of the number below it:

n! = n \times (n-1)! \qquad \text{and} \qquad 1! = 1 \;\;(\text{the base case}).

That definition translates almost word-for-word into code. Run it:

function factorial(n: number): number { if (n <= 1) return 1; // base case: 1! = 1 return n * factorial(n - 1); // recursive case: n × (n-1)! } console.log("5! =", factorial(5)); console.log("factorial(0) =", factorial(0)); console.log("10! =", factorial(10));

How does it actually run? The call stack

A recursive call doesn't finish straight away — it pauses, waiting for the smaller call to come back with an answer. The computer keeps track of these paused calls in a pile called the call stack. Calls pile up as we dive deeper, then unwind from the top once the base case is hit. Step through \text{factorial}(3) below:

The same story, written as an expanding sum. Nothing multiplies until the innermost call returns 1; then the answers ripple back out:

factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1) = 4 * 3 * 2 * 1 = 24

Recursion isn't just counting — it walks through data

Recursion shines whenever a thing is made of smaller things of the same shape. A list is a good example: it's a first item followed by another list (the rest). So to add up a list, add the first item to the sum of the rest — and the rest is a smaller list, so recursion handles it. The base case is the empty list, whose sum is 0.

function sum(numbers: number[]): number { if (numbers.length === 0) return 0; // base case: empty list sums to 0 const [first, ...rest] = numbers; // split off the first item return first + sum(rest); // first + (sum of the shorter list) } console.log(sum([1, 2, 3, 4, 5])); console.log(sum([10, 20, 30])); console.log(sum([]));

Two calls at once: Fibonacci

A recursive case can call itself more than once. In the Fibonacci sequence each number is the sum of the two before it (0, 1, 1, 2, 3, 5, 8, 13, \dots), so the recursive case makes two smaller calls. There are two base cases, for n = 0 and n = 1:

function fib(n: number): number { if (n < 2) return n; // base cases: fib(0)=0, fib(1)=1 return fib(n - 1) + fib(n - 2); // two recursive calls } for (let i = 0; i < 12; i++) { console.log("fib(" + i + ") =", fib(i)); }

Try changing the loop to go up to 40 — it crawls. Because each call spawns two more, the number of calls roughly doubles every step: computing \text{fib}(40) makes over a billion calls, most of them re-computing the same values over and over. It's a lovely example that "recursive and correct" doesn't always mean "fast". The cure — remembering answers you've already worked out, called memoisation — is a story for another page.

The number-one recursion bug is a missing or unreachable base case. If the function never hits a case that stops it, it calls itself forever — and because every paused call sits on the call stack, the stack fills up and the program crashes with a "stack overflow". This code looks reasonable but never stops, because it recurses on n — not on anything smaller:

function broken(n: number): number { if (n === 0) return 0; return broken(n); // BUG: n never gets smaller → infinite recursion }

Two habits keep you safe: always write the base case first, and make sure every recursive call moves closer to it (a smaller number, a shorter list). If it doesn't shrink, it won't stop.