Memoization

Memoization remembers answers you’ve already worked out, so a recursive function never solves the same small problem twice. It can turn hours into milliseconds. Doing the same work twice FIB(5) calls FIB(4) and FIB(3). But FIB(4) also calls FIB(3)! For FIB(40), the naive version makes over 300 million calls. Check your understanding