Solutions that call themselves: recursion

It calls itself again

A solution calling itself
sounds a little strange.
But it's simple.
To do "solve(5)"
you just do "solve(4),"
and to do "solve(4)"
you just do "solve(3)."
The same solution,
called again with a smaller input.

The same box calls itself with a smaller input. (solve(5) → solve(4) → … → solve(1))

The same box inside a box,
and the same box inside that.
Like a mirror in a mirror.
Only one thing changes,
the input shrinks one step at a time.
Shrinking and shrinking,
eventually it becomes a tiny problem
you can solve right away.

A floor to stop

If it only keeps calling itself,
what happens?
It descends forever.
So recursion must have
a floor that says
"stop here."
"When the input reaches 1,
don't call again, just answer,"
a promise like that.

With a floor vs without. (With: stops at 1 · without: descends forever)

With a floor,
it goes down, stops right there,
and climbs back up with an answer.
Without a floor,
it descends forever into 0, negatives,
and never gives an answer.
So when you use recursion,
set the floor first.

It stacks, then unwinds

How recursion builds an answer
takes two moves.
Going down,
it sets the answer aside for now
and keeps calling itself, stacking.
Once it hits the floor,
this time it climbs back up,
combining what was stacked
one by one into the answer.

Stack going down, combine back from the floor. (mul(4) = 4x3x2x1 = 24)

On the way down, the answer is hidden,
which can feel a bit frustrating.
But the moment it touches the floor,
it unwinds smoothly in reverse.
The more that's stacked,
the more to combine coming up.
So if it stacks too deep
it gets heavy,
but that's a story for later.

One with divide-and-conquer

Think back to the last lesson.
We split a big problem in half,
solved each, and merged.
That "split and solve each"
is really recursion.
solve(8)
calls solve(4) and solve(4),
and those 4s in turn
call solve(2).

Splitting as recursive calls. (solve(8) → solve(4)·solve(4) → solve(2)×4)

So divide-and-conquer and recursion
aren't separate; they're one and the same.
Splitting = calling itself again.
When a piece gets so small
it can't be split, that's the floor,
and the small answers merging upward
is the stacking and unwinding.
Everything we saw comes together here.

Recursion, in one line

Recursion has three pillars.
It calls itself with a smaller input,
it has a floor to stop,
and it stacks then unwinds back.
With just these three,
even a problem that looks complex
can be quietly handed off
to "a smaller version of itself" and solved.

The three pillars in order. (calls itself → a floor to stop → stacks, unwinds)

Just one thing to watch out for.
While splitting, sometimes the same small problem
gets solved over and over.
Figuring out the same answer again and again
wastes time.
There's a trick of writing down an answer once
and reusing it,
and that's exactly the next story.