Recursion notes

Recursion on numbers

No recursion

const add = (a, b) => {
  return a + b;
}

No base case.

No recursive case.

This is, of course, how you’d actually implement this function in Javascript.

Technically recursion

const add = (a, b) => {
  if (b === 0) {
    return a;
  } else {
    return add(a + b, 0); // 🙄
  }
}

Has a base case. (b === 0)

Has a recursive case. (Calls add)

But kinda cheating because the addition is not done by the recursion.

Was looking more for something like this

const add = (a, b) => {
  if (b === 0) {
    return a;
  } else {
    return 1 + add(a, b - 1);
  }
}

Each recursive call takes us just one step closer to the base case.

Breaking that down

Recursion is a kind of loop

Classic base case plus recursive case format:

const loop = (n) => {
   if (n === 0) {
     return;
   } else {
     console.log('hello');
     loop(n - 1);
   }
};

Logs 'hello' n times.

Simplify it a bit

const loop = (n) => {
   if (n !== 0) {
     console.log('hello');
     loop(n - 1);
   }
};

Same behavior as before.

Could be this

const loop = (n) => {
  while (n !== 0) {
    console.log('hello');
    n--;
  }
};

Another way of doing something n times.

Addition is repeated counting

We count by adding one.

For instance: 5 + 3

Start at 5 and count, i.e. add 1, three times.

5 … 6, 7, 8.

5 + 3 = 8

Using recursion to count

const add = (a, b) => {
  if (b === 0) {
    return a; // No more to count
  } else {
    // Recursive call will count from the same
    // starting number but will count one fewer
    // times since we've added the one in.
    return 1 + add(a, b - 1);
  }
}

I.e. we are adding 1 b times.

Tracing add

add(3, 2)

1 + add(3, 1)

1 + 1 + add(3, 0)

1 + 1 + 3

1 + 4

5

Hints for the next few problems

• Multiplication is repeated addition.

• Doubling is repeated multiplication by 2.

• Tripling is repeated multiplication by 3.

• Power (exponentiation) is repeated multiplication.

Recursion on arrays

The basic structure of array recursion looks like this:

const r = (array) => {
  if (array.length === 0) {
    return BASE_CASE_VALUE;
  } else {
    return COMBINE(array[0], r(array.slice(1)));
  }
}

Base case is almost always the empty array.

Combination is almost always of the first element of the array with the result of recursing on the rest of the array.

PSA

slice !== splice

Note that Javascript arrays support two methods slice and splice.

Unfortunately they do slightly different things and if you use splice when you meant slice, you will probably break your program or at least confuse yourself.

(splice modifies the array while slice does not.)

Sum

Add the numbers in an array.

const sum = (numbers) => {
  if (numbers.length === 0) {
    return 0; // the sum of no numbers is zero
  } else {
    // combine by adding
    return numbers[0] + sum(numbers.slice(1));
  }
}

Product

Multiply the numbers in an array.

const product = (numbers) => {
  if (numbers.length === 0) {
    return 1; // the product of no numbers is one
  } else {
    // combine by multiplying
    return numbers[0] * product(numbers.slice(1));
  }
}

Search

const search = (array, thing) => {
  if (array.length === 0) {
    return false; // thing is definitely not in empty array
  } else {
    // Combine by or'ing. Also have to make a
    // boolean out of the first element.
    return array[0] === thing || search(array.slice(1));
  }
}

Recursing on a tree

TreeMap

const treeMap = (tree, fn) => {
  if (isLeaf(tree)) {
    return fn(tree);
  } else {
    return {
      left: treeMap(tree.left, fn),
      right: treeMap(tree.right, fn)
    };
  }
};

Base case is when we reach a leaf of the tree.

Recursive case will recurse down each branch and then combine the results somehow.

Note that this is more complicated than a simple loop.