Some problems contain a smaller copy of themselves. Watch the calls pile up waiting, then unwind with every multiplication happening on the way home — and take the base case away to see it fall over.
Some problems contain a smaller copy of themselves. When they do, a function can solve the small copy by calling itself — and stop when the copy gets small enough to answer outright.
You have met this idea twice already without the word. Level 2: break a task into smaller tasks, and break those too. Level 12’s card sort: split the pack, sort each half, merge. Recursion is that, written down as code.
Every recursive function has exactly those two parts. A base case that answers without calling itself, and a step that makes the problem smaller and hands it back to itself. Miss either one and it never stops.
Step down to the base case, then keep stepping and watch the answers come back.
With no base case, each call adds another frame to the stack and the stack is finite memory. Eventually it runs out and the program dies with a stack overflow — which is where the website got its name.
It is the recursive twin of level 3’s infinite loop, with one difference worth knowing: an infinite loop runs forever, while infinite recursion crashes in about a second. The crash is the friendlier failure — it tells you.
Be honest about factorial: a loop does it in three lines, uses no stack, and is faster. If a loop is obvious, write the loop. Recursion is not more sophisticated and reaching for it to look clever is a real thing beginners do.
It earns its keep when the problem itself branches — when one step produces two or more smaller problems, and a loop would need you to keep track of the pending ones by hand:
Folders inside folders, the branches of a tree, working through every move in a game — all the same shape. Try writing merge sort with a loop and you will end up building a stack of your own by hand, which is exactly what recursion was doing for you.
Naive fib(n) — the one that calls itself twice — recomputes the same values an enormous number of times. Verified: fib(10) is 55, and it is instant. fib(50) written that way would take days. Correct and unusable, which is level 6 of the thinking track arriving for the last time.
Ask the person behind: “how many people are behind you, including yourself?” When they answer, add one and pass it forward.
The last person has nobody behind them. They answer 1 without asking anyone. That is the base case, and without it the question goes on forever.
Two people can do it with objects in a line. What you feel is the shape: the question travels all the way to the end before a single answer comes back, and then the additions happen on the way home. Take the last person away and the question never returns — which is a stack overflow, performed by humans.
Fourteen levels. You can set up a Mac to compile, read the compiler when it complains, declare and use the five types, do arithmetic without losing halves, make decisions, repeat things, write your own functions, hold lists of values, work with text, save to files, design your own types, follow a pointer, and write a function that calls itself.
That is a first computer science course. Not a preview of one — the content of one. And you did the thinking first, which is the part most people skip and then quietly struggle without.
Go back to the thinking track whenever something in class feels impossible — nine times out of ten the problem is not the C++, it is that the problem has not been broken down yet. And keep the error notebook from level 3. By week eight it will be the most useful thing you own.
Write the stopping condition before the recursive call, every time, without exception.
Nothing is computed going down. Every call waits, and the work happens coming back.
If a loop is obvious, write the loop. Recursion is for problems that split into several smaller ones.
Not recall — these are the shapes an exam actually uses. Every answer below was produced by compiling and running the code, so if you disagree with one, the compiler is the one to believe.
Have a real go before revealing. Being wrong here is worth more than being right in three weeks.
What does this print?
You delete the if (n <= 1) return 1; line. What happens?
When is recursion a worse choice than a loop?
← back to the whole C++ track · stuck on anything? ask peter.