Nib asked, and Nib — askNib's tutor — drew the answer live at a whiteboard. This is the spoken transcript; enable JavaScript to watch it drawn.
What is dynamic programming, really? (for a curious adult who has seen a little code but never studied algorithms). Cover, in this order: What does it mean for a function to call itself?; Why does the obvious Fibonacci recursion explode?; What if you remember each answer the first time?; Can you skip the recursion and fill in a table instead?; What makes a problem fit this trick?; How do you use it on a brand-new problem, like fewest coins? — page 1: A Function That Calls Itself
Sum of one through four is four plus the sum of one through three. The same question, just smaller.
sum of n is n plus sum of n minus one. Each call holds its own n and waits for the smaller call to return before it can finish.
This recursion never stops on its own. Sum of one is just one, so that's the base case: return the answer directly, with no further calls.
Trace it: four calls three, calls two, calls one, which returns one. Then answers climb back: three, six, ten.
Every recursive function has two parts: a recursive case that shrinks the problem, and a base case that stops it.
Recursion is just a function trusting a smaller copy of itself, with a base case to end the chain. Next, we'll see how this innocent idea can explode.