The thing that trips people up#
Most people meet recursion and try to trace it. They follow the first call into the second, the second into the third, and somewhere around the fourth they lose their place and decide recursion is hard.
Tracing is the wrong move. You do not trace a loop by unrolling a thousand iterations in your head; you read the loop body and the condition. Recursion has the same two parts, and reading them is all you have to do.
The two parts#
The base case. The smallest input, where the answer is known outright and no further call is made.
The recursive step. One move that makes the problem smaller, plus the assumption that the same function already solves the smaller version correctly.
That assumption feels like cheating. It is not. It is the same assumption you make with a loop invariant, just written the other way round.
length(node):
if node is null: # base case
return 0
return 1 + length(node.next) # one step, then trust
Read that as a sentence: the length of a list is one, plus the length of whatever follows. It never needed tracing.
Where the paperwork goes#
A function that calls itself does not overwrite itself. Each call gets its own stack frame, holding its own arguments and its own place to come back to. Those frames pile up, and they come off in reverse order: last in, first out. That arrangement is called a stack, and it gets a lesson of its own later. Nothing here needs more of it than the picture of a pile.
This has two consequences worth remembering.
It costs memory. A recursion n calls deep holds n frames. On a linked list of a hundred thousand nodes, a recursive length blows the stack and the program stops. A loop does the same job in one frame.
There is a moment on the way back. Code before the recursive call runs on the way down; code after it runs on the way up. That is the whole difference between preorder and postorder on a tree, and it is why "reverse a linked list recursively" looks strange at first: the rewiring happens on the way back.
Drawing the calls#
Once a function calls itself more than once, the calls stop being a line and become a tree:
fib(5)
├── fib(4)
│ ├── fib(3)
│ │ ├── fib(2)
│ │ └── fib(1)
│ └── fib(2)
└── fib(3)
├── fib(2)
└── fib(1)
Draw that for fib(5) and something jumps out: fib(3) is computed twice, fib(2) three times. The tree is doing the same work over and over, and it doubles in size with every step of n.
That picture is the start of dynamic programming. Every DP solution begins as a recursion whose tree repeats itself, and the fix is to write each answer down the first time. You do not need that today, but you should recognise the shape when you meet it later.
When recursion is the right tool#
Reach for it when the data is defined in terms of itself. A tree is a node with two trees hanging off it. A linked list is a node with a list after it. A directory holds files and more directories. Code that mirrors the shape of its data is shorter and much harder to get wrong.
Reach for a loop when the problem is a flat sequence and the depth could be large. Walking an array, counting digits, scanning a string: a loop says it plainly and uses one frame.
Getting one right#
- Name the base case first, before anything else.
- Write the step as a single sentence in English.
- Convince yourself the input really does get smaller each time. If it does not, the base case is never reached and you get a stack overflow, which is the recursive version of an infinite loop.
- Only then write the code.
Practice in order#
- Reverse a linked list, which is where the "on the way back" moment becomes concrete.
- Maximum depth of a binary tree, the shortest recursion you will ever write.
- Same tree and invert a binary tree, both one step plus trust.
- Climbing stairs, where the tree repeats itself and you will want to write the answers down.