What is recursion

A function that calls itself

In Lesson 9, a function was a bundle of tasks with a name, and a function could call other functions.
Recursion goes one step further: a function calls itself again.
Like a mirror inside a mirror, the same thing appears one more layer deep.

Each time you press "one more layer," the same frame appears one layer further in.

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

There has to be a place to stop

Two mirrors really do go on forever, but a computer can't do "forever."
So you set a rule: "Once the piece is small enough, stop there."
Without this stopping rule, it goes around endlessly and collapses.

Turn the stopping rule on and it stops neatly at 3, 2, 1. Turn it off and it keeps going down until it collapses.

It helps to think of the stopping point as the "bottom."
Until it reaches the bottom, it keeps calling itself; once it reaches the bottom, it stops calling.
The key question, then, is how to split the problem.

A smaller version of the same problem

The real secret of recursion is seeing a big problem as "one step + the same problem, only smaller."
A whole staircase is one step plus the rest of the stairs, and the rest of the stairs is the same problem, just one step smaller.
It gets smaller and smaller until it reaches 0 steps, and then it's done.

Each time you press "remove one step," the staircase loses a step. What's left is always "the same, only smaller."

Suddenly a hard problem becomes easy.
You don't have to solve it all at once: handle just "one step" and hand the rest back to the same function.
But how does the work you handed off come back?

Going down and coming back up

Recursion moves in two directions.
First it goes all the way down to the bottom, calling itself again and again.
Once it reaches the bottom, it climbs back up, and each level adds its own share.
It's just like stacking plates and then clearing them from the top.

Press "next step" to go down to the bottom of 1+2+3 and then come back up, gathering it into 6.

This "down and back up" is the heart of recursion.
On the way down, it splits the problem; on the way up, it combines the answers.
The stacked-up work unwinds in order from the bottom.

Loops' sibling, and beyond

Recursion and loops (Lesson 7) are siblings.
Both do the same thing many times, but a loop lays it out side by side, while recursion digs inward one layer at a time.
For things where branches grow more branches, like folders inside folders, recursion is a perfect fit.

Each press makes the branches split again. The same rule draws a tree by itself.

The function that bundles tasks under a name (Lesson 9) can now even call itself.
Split it small, stop at the bottom, gather it back up: this one idea handles folders, replies to replies, and even solving mazes.
In the next lesson, we'll move on to storing values in pairs.