Recursion
A function that calls itself on a smaller input, and the stack of parked frames that makes that work.
A recursive function answers a problem by calling itself on something smaller and stopping at a case it can answer outright. Each call gets a frame on the call stack holding its arguments and its position in the code, and that frame stays parked until the call it made returns. That is the entire mechanism, and it is why a recursion 10,000 deep holds 10,000 frames of memory where a loop holds none.
Two parts have to be right together. The recursive case must move strictly towards the base case, and the base case must exist and be reachable from every input. A call that recurses on n instead of n - 1, or that tests n == 0 when n can go negative, does not hang harmlessly: it fills the stack and the process dies.
The shape of the calls is the running time. One call per frame is a chain and costs the depth. Two calls per frame is a tree that doubles at every level, so the plain recursive Fibonacci makes on the order of 2^n calls to produce one number. Drawing that tree shows both the cost and the repetition, and the repetition is precisely what a cache removes.
After this you can
- Trace a recursion frame by frame and say what each parked frame is waiting for
- Write a base case that is always reached and a recursive case that always shrinks the input
- Draw a recursion tree and read the number of calls off its branching and its depth
- Turn a tail call into a loop, or any recursion into an explicit stack
- Add a cache to a recursion and say which arguments belong in the key
The list starts with 3. Keep it, and call sum on the remaining 4 numbers. A smaller problem each time.
In this order
- RecursionA function that calls itself on a smaller input until a base case, each call parked as a frame until the one above it returns.
- Base Case and Recursive CaseThe recursive case shrinks the problem and the base case stops it; without a base case the stack overflows.
- Recursion TreeEvery call is a node, every recursive call a child; the size of the tree is the running time.
- Tree RecursionA function that makes more than one recursive call, so its calls form a tree that doubles with n.
- Memoized RecursionCache results by argument; a repeated call becomes a leaf that returns at once.
- Tail RecursionThe recursive call is the last action, so the frame can be reused and the stack never grows.
- Recursion to IterationA tail call is a loop in disguise: replace the call with an update of the arguments and jump back.
Where people go wrong
A base case that is never reached
Testing n == 0 while the recursive call subtracts 2 steps straight past it for odd n. The base case has to cover every way the input can become small, which usually means n <= 0 rather than n == 0.
Counting the stack as free
Every parked frame holds its arguments and locals. One frame per element over a million-element list is a million frames, and most runtimes stop somewhere around ten thousand. The depth of a recursion is its space complexity, not a detail.
Expecting tail calls to be optimised away
A tail call can reuse its frame, but only if the language actually does it. C compilers usually will at higher optimisation levels, Python never does, and most JavaScript engines do not. Rely on it and the stack still grows.
Or a different category
Dynamic Programming
The recursion tree keeps asking the same question, so the answers are worth storing in a cache or a table.
Stack and Queue Algorithms
You want the explicit stack itself, pushing your own frames to control the order or to dodge a depth limit.