Recursion
A function that calls itself on a smaller input, and the stack of parked frames that makes that work.
The Call Stack: Summing a list recursively
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
In this order
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.