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
fib(n): the n-th Fibonacci number, memoized so thatfib(70)returns instantly.binarySearch(sorted, target): the index oftargetin the sorted array, or-1if 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.