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

Nib asked for

A Function That Calls Itself

the short answer

A recursive function solves a problem by calling itself on a smaller version of the same problem, and it stops at a base case that needs no further calls.

5 steps, drawn by Nib. Read it here, or watch him draw it. Updated 16 Oct 2026.

1same, but smaller

Imagine you want the sum of 1 through 4. You could add them in a loop. Or you could notice a shortcut in the wording: the sum of 1 through 4 is 4 plus the sum of 1 through 3. That second piece is the same kind of question, just smaller. Recursion means writing a function that answers a question by asking itself that smaller question.

Solve a problem by asking the same question on something smaller.

a common mix-upCalling itself sounds circular or paradoxical, as if the function defines itself with nothing underneath.

2the call stack

Here is the function: sum(n) returns n + sum(n - 1). Each call hands the leftover work to a new call with a smaller number. The function waits while that new call runs, and the new call is a fresh copy with its own n. Nothing magical happens; it is an ordinary function call that happens to name the same function.

A self-call is just a normal call, with its own fresh n.

check yourself

If sum(3) is running, what value of n does the call it makes have?

Show the answer

2, because it calls sum(n - 1).

3base case

As written, this never stops: sum(1) would call sum(0), then sum(-1), forever. We need a spot where the function answers directly with no further call. For summing, sum(1) is simply 1. That is the base case: the smallest version, so simple the answer is known outright. Without it the calls pile up until the program crashes.

The base case is the smallest problem, answered without calling again.

a common mix-upPeople think recursion runs forever by nature; it only does when the base case is missing or never reached.

4down then up

Now trace sum(4). It calls sum(3), which calls sum(2), which calls sum(1), which hits the base case and returns 1. Then the answers travel back up: sum(2) is 2 + 1 = 3, sum(3) is 3 + 3 = 6, sum(4) is 4 + 6 = 10. Going down, the problem shrinks; coming back up, the answers get assembled.

Calls go down to the base case; answers come back up and combine.

check yourself

What would sum(5) return, given sum(4) is 10?

Show the answer

15, since it is 5 + sum(4).

5two parts

So every recursive function needs two parts. The recursive case makes the problem smaller and trusts the self-call to handle it. The base case ends the shrinking. Check both whenever you write one: does each call truly get smaller, and does the smallest case have a direct answer? Later pages rely on exactly this shape.

Two parts: a recursive case that shrinks, and a base case that stops.

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.