TypeScript Recursion

A function that calls itself

Recursion is when a function calls its own name. Each call works on a smaller piece of the problem, then waits for that inner call to finish. The inner call may call again. That chain has to stop.

The stop condition is the base case: a path that returns without calling the function again. Every recursive function you write in this tutorial has one.

Countdown

countdown prints n, then calls itself with n - 1. Whenn is 0 or less, it prints done and returns. That is the base case.

function countdown(n: number): void {
  if (n <= 0) {
    console.log("done");
    return;
  }
  console.log(n);
  countdown(n - 1);
}

countdown(3);

Output is 3, then 2, then 1, then done.

The base case comes first

Check the stop condition before you recurse. If you recurse first, the function never reaches the return. For countdown, the question is: is n already at zero? If yes, stop. If no, print and go one step smaller.

• Base case: n <= 0 — no further call.
• Recursive case: print n, then countdown(n - 1).

The argument must move toward the base case. Here it decreases by one. If it stayed the same, you would never stop even with a base case written in the file.

Factorial

Factorial of n is n * (n - 1) * ... * 1. In code: if n is 0 or 1, the answer is 1. Otherwise it is n times factorial of n - 1.

function factorial(n: number): number {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(5));

factorial(5) waits for factorial(4), which waits for 3, then 2, then 1. The base case returns 1. Then 2 * 1, 3 * 2, 4 * 6, 5 * 24. The program prints 120.

Sum an array from the front

Recursion is not only numbers counting down. You can take the first item, then recurse on the rest. The base case is an empty list: the sum is 0.

function sumFrom(nums: number[], start: number): number {
  if (start >= nums.length) {
    return 0;
  }
  return nums[start] + sumFrom(nums, start + 1);
}

const values: number[] = [3, 4, 5];
console.log(sumFrom(values, 0));

sumFrom(values, 0) is 3 plus the sum from index 1, which is 4 plus the sum from index 2, which is 5 plus 0. The program prints 12. start moves toward nums.length.

A missing base case crashes

Each call uses a frame on the call stack. If there is no base case, or the argument never reaches it, frames pile up until the program dies. tsc will not catch this at compile time. You get a runtime crash, often labeled a stack overflow.

function forever(n: number): void {
  console.log(n);
  forever(n + 1);
}

Recursion or a loop

Countdown is also a for or while. A loop does not grow the stack. Prefer a loop when the steps are a simple counter. Recursion is clearer when a problem splits into a smaller copy of itself, such as walking a tree. For this tutorial, factorial and countdown are enough to see the pattern.

Next: objects that bundle data and the functions that work on it.