Lesson 14 of 14 · 15 min

Recursion, memoization and searching

Recursion

A function that calls itself is recursive. It needs two parts: a base case that answers directly, and a recursive case that breaks the problem into a smaller version of itself:

function factorial(n) {
  if (n <= 1) return 1;          // base case
  return n * factorial(n - 1);   // smaller problem
}
factorial(5);  // 5 * 4 * 3 * 2 * 1 = 120

Memoization

The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13...: each is the sum of the two before. The direct recursive version is short but painfully slow, because it works out the same values again and again (fib(50) makes billions of calls).

Memoization fixes this: remember each answer the first time, and look it up next time.

const cache = new Map();
function slowSquare(n) {
  if (cache.has(n)) return cache.get(n);
  const result = n * n;  // imagine this were expensive
  cache.set(n, result);
  return result;
}

Binary search

Finding a value by checking every item takes up to a million steps in a million items. If the array is sorted, you can do far better: look at the middle item. If the target is bigger, it must be in the right half; if smaller, the left half. Each step halves what is left, so a million items need only about 20 steps.

Your task

  1. fib(n): the n-th Fibonacci number, memoized so that fib(70) returns instantly.
  2. binarySearch(sorted, target): the index of target in the sorted array, or -1 if it is not there. It must halve the search range each step.

Programs that run for more than 10 seconds are stopped, so an un-memoized fib(70) will not finish.

main.js
function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);   // correct, but far too slow for fib(70)
}

function binarySearch(sorted, target) {
  // return the index of target, or -1
}

console.log(fib(30));
console.log(binarySearch([1, 3, 5, 7, 9], 7));

Discussion

Stuck? Ask here. Be kind, and share hints rather than full answers.

Loading the discussion…