Section Recap

You have learned recursion. You understand base cases, recursive cases, and the call stack. You can trace recursive calls and write recursive code.

You have seen single-parameter recursion (factorial, sum of digits) and two-parameter recursion (GCD). You have seen linear recursion ($n \to n-1$) and logarithmic recursion ($n \to n/2$). Good job. Now you are ready for the next level: making recursion fast. Right now, $\text{factorial}(100)$ works fine.

But some recursive solutions repeat the same work millions of times. The fix is called memoization. I will show you exactly how it works in the next section.