Learn/TypeScript/11. Recursion
Lesson 11 of 15
Sign in

TypeScript, lesson 11

Recursion

A recursive function solves a problem by calling itself on a smaller version of the same problem. It suits data that contains smaller copies of itself, such as folders inside folders or replies to replies, and problems that split naturally into sub-problems.

Base case and recursive case

Every recursive function needs both:

  • a base case that it answers directly, without calling itself;
  • a recursive case that makes the problem smaller and calls itself.

Each call waits on the call stack with its own parameters until the calls below it return. The stack is limited (roughly ten thousand levels in Deno, depending on how much each call stores). Missing base cases or steps that do not shrink the problem end with RangeError: Maximum call stack size exceeded. When a plain loop is just as clear, as it is for power, prefer the loop.

Recursive types

TypeScript types can refer to themselves, which is exactly what nested data needs:

2 exercises to try what you just read.

Exercise 1

Folder sizes

Press Ctrl Enter or Check to test your code.

Exercise 2

Tower of Hanoi

Press Ctrl Enter or Check to test your code.

The shape of the type tells you the shape of the function: one call per comment, and a loop over replies that recurses.

The base case is hidden in the data: a comment with an empty replies array makes no further calls. Trust the recursive call to handle a whole subtree correctly (the leap of faith), and only check that you combine the results correctly.

Passing information down

Results flow up through return values. Information can flow down through extra parameters, such as the current depth, which is handy for indented printing:

Parsing nested JSON

JSON.parse returns any, which silently switches type checking off. A safer habit is to state the type you expect: const root: Comment = JSON.parse(text);. This is a promise you make to the checker, not a run-time check, so it is only as good as your input. For data from untrusted sources you would validate the shape first.

Splitting into several sub-problems

Some problems need more than one recursive call. In the Tower of Hanoi puzzle, moving n disks from one peg to another means: move n - 1 disks out of the way, move the biggest disk, then move the n - 1 disks back on top. Two recursive calls, each on a smaller problem, and a base case of zero disks (nothing to do). The number of moves doubles with each extra disk, so n = 20 already needs over a million moves: recursion can describe enormous amounts of work in a few lines.

Further reading

  • MDN: Functions guide, recursion
  • TypeScript Handbook: Object Types
  • TypeScript Handbook: Everyday Types, any

A folder tree is given as one line of JSON. Each entry has a name; files also have a size (in KB), and folders have children instead. Print the tree, indenting each level by two spaces, with every file shown as NAME SIZE and every folder shown as NAME/ TOTAL, where TOTAL is the sum of all file sizes inside it at any depth.

Sample input:

Sample output:

Three pegs are named A, B and C. N disks of different sizes sit on peg A, the largest at the bottom. Move them all to peg C, one disk at a time, never putting a larger disk on a smaller one. Write a recursive function hanoi(n: number, from: string, to: string, via: string): void that prints every move as disk D: X -> Y (disks are numbered 1 for the smallest to N for the largest). Afterwards, print Total moves: N.

The input is N, from 0 to 10.

Sample input:

Sample output:

function power(base: number, exp: number): number {
  if (exp === 0) return 1;                 // base case
  return base * power(base, exp - 1);      // smaller problem: exp - 1
}
console.log(power(2, 5));   // 32
interface Comment {
  author: string;
  text: string;
  replies: Comment[];      // a comment contains more comments
}
function countComments(c: Comment): number {
  let total = 1;                              // this comment
  for (const reply of c.replies) {
    total += countComments(reply);            // plus everything below each reply
  }
  return total;
}
function show(c: Comment, depth = 0): void {
  console.log(`${"  ".repeat(depth)}${c.author}: ${c.text}`);
  for (const reply of c.replies) show(reply, depth + 1);
}
{"name":"home","children":[{"name":"notes.txt","size":4},{"name":"photos","children":[{"name":"cat.jpg","size":120},{"name":"dog.jpg","size":95}]}]}
home/ 219
  notes.txt 4
  photos/ 215
    cat.jpg 120
    dog.jpg 95
2
disk 1: A -> B
disk 2: A -> C
disk 1: B -> C
Total moves: 3