TypeScript, lesson 11
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.
Every recursive function needs both:
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.
TypeScript types can refer to themselves, which is exactly what nested data needs:
2 exercises to try what you just read.
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.
Results flow up through return values. Information can flow down through extra parameters, such as the current depth, which is handy for indented printing:
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.
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.
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)); // 32interface 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 952disk 1: A -> B
disk 2: A -> C
disk 1: B -> C
Total moves: 3