Recursion Trees

Every call is a node

Lesson 14 taught recursion as “a function that calls itself on a smaller problem”. Part 8 builds on this, so you need one more picture: the recursion tree. It is like a family tree. Draw every call as a node (a dot or box). Draw an arrow from a call to each call it makes. These are its children. The first call is the root. Calls that stop at the base case (the simplest case, which needs no more calls) are the leaves.

Once you can draw that tree, three questions become easy. What does this function return? Read the leaves, then combine the answers going up. How long does it take? Count the nodes. How much memory does it use? Look at the height of the tree, because that is how many calls are open at the same time.

Drawing a recursion tree

For Fibonacci, each call makes two children: fib(n − 1) and fib(n − 2).

function fib(n) {  if (n <= 1) return n;          // base case: stop here  return fib(n - 1) + fib(n - 2);   // two smaller problems}console.log(fib(4)); // 3

                    fib(4)                  /        \             fib(3)          fib(2)            /      \        /     \        fib(2)    fib(1)  fib(1)  fib(0)        /    \    fib(1)  fib(0)

To draw the tree, follow these steps. Write the first call. Below it, write each call it makes. Repeat this for every node that is not a base case. At the leaves, write the base-case value. Then work back up. The value of each node is made from its children (here, the sum of the two).

Traced: the calls of fib(4)

▶function fib(n) {2  if (n <= 1) return n;3  const a = fib(n - 1);4  const b = fib(n - 2);5  return a + b;6}7console.log(fib(4));

Reading cost off the tree

General rule: if each call makes b calls and the tree has height h, there are about bh nodes. Fibonacci makes 2 calls each time and has height n, so the tree has at most about 2ⁿ nodes. That means O(2ⁿ) time (roughly, the time doubles every time n grows by 1) and O(n) space. (The exact count grows a little slower, about 1.6ⁿ, because the right side of the tree is shorter. It is still exponential growth.) A function that makes one call per level over n levels (like the sum below) has n nodes, so it takes O(n) time and O(n) space.

Passing answers down vs returning answers up

Information can travel through the tree in two ways.

• Return-based: each call returns its answer, and the parent combines the answers. The answer is built on the way up. (Examples: sum, Fibonacci, tree height.)
• Parameter-based: each call receives what has been decided so far as parameters (the values you pass in). The answer is complete at the bottom. The answer travels down. (Examples: a running total, the current path, a result list shared by all calls.)

// Return-based: the answer is built on the way back UP.function sumReturn(arr, i = 0) {  if (i === arr.length) return 0;            // nothing left to add  return arr[i] + sumReturn(arr, i + 1);     // my value + the sum of the rest}// Parameter-based: the answer is carried DOWN and given back at the bottom.function sumParam(arr, i = 0, total = 0) {  if (i === arr.length) return total;        // the total we collected is the answer  return sumParam(arr, i + 1, total + arr[i]);}console.log(sumReturn([3, 1, 4])); // 8console.log(sumParam([3, 1, 4]));  // 8

You will use parameter-based recursion when you need to list things, such as all subsets or all permutations (the next two lessons). The parameters hold the choices made so far. At a leaf, you save the finished choice.

// Parameter-based with one shared result list: common when you must list everything.function evensUpTo(n) {  const out = [];  (function go(i) {    if (i > n) return;    if (i % 2 === 0) out.push(i);    go(i + 1);  })(0);  return out;}console.log(evensUpTo(7)); // [0, 2, 4, 6]

Many recursive calls

When a function makes two or more recursive calls per node, the tree spreads out like a fan. There are two cases.

• Independent subproblems (merge sort cuts the array into two halves): the pieces do not overlap, so the total work stays small: O(n log n).
• Overlapping subproblems (Fibonacci): the same sub-tree appears many times, so you do the same work again and again. Memoisation (remembering answers you already worked out, Part 14) removes this repeated work.

Tower of Hanoi is the classic puzzle with 2 calls per node and no overlap. To move n disks, first move n − 1 disks out of the way. Then move the big disk. Then move the n − 1 disks back on top. The calls that move a disk number 2ⁿ − 1, one per move, so the number of moves is exactly 2ⁿ − 1 (Practice question 4).

Fast power: a tree that is one straight line

To work out xⁿ (n copies of x multiplied together), the simple way takes about n multiplications. For example, 2³ = 2 × 2 × 2 = 8. But xⁿ = (x^n/2)². So make one recursive call on half the exponent (the small raised number n) and reuse its result. The tree is then one chain of about log₂ n calls. (log₂ n means how many times you can halve n before you reach 1.)

function myPow(x, n) {  if (n < 0) return 1 / myPow(x, -n);       // a negative power means 1 divided by the positive power  if (n === 0) return 1;                    // base case: x^0 = 1  const half = myPow(x, Math.floor(n / 2)); // ONE call on half the size  return n % 2 === 0 ? half * half : half * half * x;}console.log(myPow(2, 10));  // 1024console.log(myPow(2, -2));  // 0.25console.log(myPow(2, 31));  // 2147483648

Preview: the cost of repeating work

Let us count the calls. The simple Fibonacci tree for fib(30) has 2,692,537 nodes. If you remember each answer the first time you work it out, the tree shrinks to 59 nodes.

let calls = 0;function fibNaive(n) {  calls++;  return n <= 1 ? n : fibNaive(n - 1) + fibNaive(n - 2);}console.log(fibNaive(20), calls); // 6765 21891calls = 0;const memo = new Map();function fibMemo(n) {  calls++;  if (n <= 1) return n;  if (memo.has(n)) return memo.get(n);        // already solved: reuse the answer  const value = fibMemo(n - 1) + fibMemo(n - 2);  memo.set(n, value);  return value;}console.log(fibMemo(30), calls); // 832040 59

This is memoisation (also spelled memoization). It means remembering the answer of a call, so that the same call is never worked out twice. You keep a Map (a lookup table of key and value pairs) from the inputs to the answers, and you check it at the top of the function. It helps whenever the same call can appear in more than one place in the tree. You will learn it fully in Part 14. For now, just see that the recursion tree shows you when it will help: look for sub-trees that appear more than once.

Practice questions

For every question, draw the tree for a very small input before you write any code.

function fib(n) {  if (n <= 1) return n;  return fib(n - 1) + fib(n - 2);}console.log(fib(2));  // 1console.log(fib(4));  // 3console.log(fib(10)); // 55

function fib(n, memo = new Map()) {  if (n <= 1) return n;  if (memo.has(n)) return memo.get(n);  const value = fib(n - 1, memo) + fib(n - 2, memo);  memo.set(n, value);  return value;}console.log(fib(30));  // 832040console.log(fib(50));  // 12586269025

function fib(n) {  let a = 0, b = 1;               // fib(0), fib(1)  for (let i = 0; i < n; i++) {    [a, b] = [b, a + b];  }  return a;}console.log(fib(10)); // 55console.log(fib(0));  // 0console.log(fib(50)); // 12586269025

function myPow(x, n) {  if (n < 0) { x = 1 / x; n = -n; }  let result = 1;  for (let i = 0; i < n; i++) result *= x;  return result;}console.log(myPow(2, 10)); // 1024console.log(myPow(2, -2)); // 0.25

function myPow(x, n) {  if (n < 0) return 1 / myPow(x, -n);  if (n === 0) return 1;  const half = myPow(x, Math.floor(n / 2));  return n % 2 === 0 ? half * half : half * half * x;}console.log(myPow(2, 10)); // 1024console.log(myPow(2, -2)); // 0.25console.log(myPow(2, 0));  // 1console.log(myPow(2, 31)); // 2147483648

function myPow(x, n) {  if (n < 0) { x = 1 / x; n = -n; }  let result = 1;  while (n > 0) {    if (n % 2 === 1) result *= x;   // this binary digit of the exponent is 1    x *= x;                         // x, x^2, x^4, x^8, ...    n = Math.floor(n / 2);  }  return result;}console.log(myPow(2, 10)); // 1024console.log(myPow(2, -2)); // 0.25console.log(myPow(3, 5));  // 243

function kthGrammar(n, k) {  let row = "0";  for (let i = 1; i < n; i++) {    row = [...row].map((c) => (c === "0" ? "01" : "10")).join("");  }  return Number(row[k - 1]);}console.log(kthGrammar(1, 1)); // 0console.log(kthGrammar(2, 2)); // 1console.log(kthGrammar(4, 5)); // 1

function kthGrammar(n, k) {  if (n === 1) return 0;  const parent = kthGrammar(n - 1, Math.ceil(k / 2));  return k % 2 === 1 ? parent : 1 - parent;}console.log(kthGrammar(1, 1));            // 0console.log(kthGrammar(2, 1));            // 0console.log(kthGrammar(2, 2));            // 1console.log(kthGrammar(4, 5));            // 1console.log(kthGrammar(4, 6));            // 0console.log(kthGrammar(30, 434991989));   // 0

function hanoi(n, from, to, via, moves = []) {  if (n === 0) return moves;  hanoi(n - 1, from, via, to, moves);     // clear the way  moves.push(from + "→" + to);            // move the biggest disk  hanoi(n - 1, via, to, from, moves);     // put the other disks back on top  return moves;}console.log(hanoi(1, "A", "C", "B").join(", ")); // A→Cconsole.log(hanoi(2, "A", "C", "B").join(", ")); // A→B, A→C, B→Cconsole.log(hanoi(3, "A", "C", "B").length);     // 7console.log(hanoi(10, "A", "C", "B").length);    // 1023

function binaryStrings(n) {  const out = [];  function build(prefix) {    if (prefix.length === n) { out.push(prefix); return; }    build(prefix + "0");    build(prefix + "1");  }  build("");  return out;}console.log(binaryStrings(2));        // ["00","01","10","11"]console.log(binaryStrings(3).length); // 8

function flatten(arr) {  const out = [];  for (const x of arr) {    if (Array.isArray(x)) out.push(...flatten(x));    else out.push(x);  }  return out;}console.log(flatten([1, [2, [3, [4]], 5]])); // [1, 2, 3, 4, 5]console.log(flatten([[], [1], [[2]]]));      // [1, 2]

function flatten(arr) {  const out = [];  const stack = [...arr];  while (stack.length > 0) {    const x = stack.pop();    if (Array.isArray(x)) stack.push(...x);    else out.push(x);  }  return out.reverse();              // popping goes from right to left, so reverse at the end}console.log(flatten([1, [2, [3, [4]], 5]])); // [1, 2, 3, 4, 5]console.log(flatten([]));                    // []

function fibCalls(n) {  if (n <= 1) return 1;                         // a leaf: one call  return 1 + fibCalls(n - 1) + fibCalls(n - 2); // me + both sub-trees}console.log(fibCalls(4));  // 9console.log(fibCalls(20)); // 21891console.log(fibCalls(30)); // 2692537

function fibCallsFast(n) {  let a = 0, b = 1;                  // fib(0), fib(1)  for (let i = 0; i <= n; i++) [a, b] = [b, a + b];   // after the loop, a = fib(n + 1)  return 2 * a - 1;}console.log(fibCallsFast(4));  // 9console.log(fibCallsFast(20)); // 21891console.log(fibCallsFast(30)); // 2692537

Make it stick

What's next

With recursion trees you can see how a function explores all the options. Lesson 33 uses a tree whose branches are choices: pick an item or skip it. The leaves of that tree are all the subsets, permutations and combinations.