How does recursion work in algorithms

Calling itself again

A method that calls itself sounds a little strange, but it's simpler than it seems.
To solve "solve(5)," you solve "solve(4)," and to solve "solve(4)," you solve "solve(3)."
The same method is called again with a smaller input.

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

Inside the box is an identical box, and inside that, another identical box, like mirrors within mirrors.
Only one thing changes: the input gets smaller by one each time.
As it keeps shrinking, it eventually becomes a tiny problem you can solve right away.

The floor where it stops

What happens if a method just keeps calling itself? It goes down forever.
That's why recursion must always have a floor that says "stop here."
A promise like "when the input reaches 1, don't call again; just answer."

Compare having a floor vs having none. With one, it stops at 1; without one, it goes down forever.

With a floor, the calls go down, stop right there, and carry the answer back up from that point.
Without one, they sink endlessly into 0 and the negatives, and no answer ever comes out.
So when you use recursion, decide on the floor first.

Stacking up, then unwinding

Recursion builds its answer in two moves.
On the way down, it puts off the answer for now and keeps calling itself, stacking the calls up.
Once it hits the floor, it climbs back up, combining what it stacked one by one to complete the answer.

Stack up on the way down, then combine in reverse from the floor. (mul(4) = 4x3x2x1 = 24)

On the way down, the answer isn't visible yet, which can feel a bit frustrating.
But the moment it touches the floor, everything unwinds smoothly in reverse. The more that stacked up, the more there is to combine on the way back.
It's also worth remembering that if the stack grows too deep, even a computer struggles.

One with divide and conquer

Think back to the last lesson. We split a big problem in half, solved each half, and combined them.
That "split and solve each part" is actually recursion.
solve(8) calls solve(4) and solve(4), and each solve(4) in turn calls solve(2) twice.

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 yourself again.
When a piece gets too small to split, that's the floor, and the small answers combining upward are the stacking and unwinding.
Everything we've seen so far comes together here.

Recursion in one line

Recursion stands on three pillars: it calls itself with a smaller input, it has a floor where it stops, and it stacks up and then unwinds in reverse.
With these three in place, even a problem that looks complicated can be quietly handed off to "a smaller me" and solved.

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

There's one thing to watch out for, though. As you split, you sometimes end up solving the same small problem over and over.
Finding the same answer again and again wastes time.
There's a trick for writing down an answer once and reusing it, and that's the next story.