A function that calls itself: recursion

A function that calls itself

In lesson 9, a function bundled work and got a name.
Inside it, you could call other functions.
Recursion goes one step further:
the function calls itself again.
Like a mirror inside a mirror, the same thing appears one layer deeper.

Tap it. Each tap adds one more identical frame inside.

It's neat, but a little scary too.
If it keeps calling itself like this,
won't it go on forever?
Exactly. So recursion needs one essential thing.

It needs a place to stop

Two mirrors really do go in forever,
but a computer can't do 'forever'.
So we set one rule:
'when the piece is small enough, stop there.'
Without this stop rule, it spins forever and crashes.

Turn the stop rule on and it halts at 3, 2, 1. Turn it off and it falls forever and breaks.

Think of this stopping spot as 'the floor'.
Until it reaches the floor, it keeps calling itself;
once it touches the floor, it stops calling.
Now the key is how we break things down.

A smaller version of the same problem

Here's the real trick of recursion.
See a big problem as 'one step + the same problem, but smaller'.
The whole staircase = one stair + the rest of the staircase.
The 'rest' is the same problem, just one stair smaller.
It shrinks and shrinks until it reaches 0 stairs.

Peel off one stair at a time. What's left is each time 'the same but smaller' problem.

A hard problem suddenly gets easy.
You don't have to solve all of it at once.
Just handle 'one stair' and hand the rest back to the same function.
But how does the handed-off work come back?

Down, then back up

Recursion moves in two directions.
First it goes all the way down to the floor (calling itself, again and again).
Once it hits the floor, it climbs back up,
each level adding its own part.
Just like stacking plates, then clearing them from the top back down.

Step through it. It goes down to the floor for 1+2+3, then climbs back up gathering 6.

This 'down then up' is the heart of recursion.
Going down, it splits the problem;
coming up, it combines the answers.
The piled-up work unwinds from the floor, one by one.

The loop's sibling, and beyond

Recursion and the loop (lesson 7) are siblings.
Both 'do the same thing many times', but
a loop lays them out side by side,
while recursion digs inward layer by layer.
For folders inside folders, or branches splitting into branches, recursion fits perfectly.

Each tap splits a branch again. The same rule draws a whole tree by itself.

The function we bundled and named (lesson 9)
can now even call itself.
Split small, stop at the floor, gather back up.
This one idea unlocks folders, replies-to-replies, even solving mazes.
Next, we'll go to pairing and storing many values together.