Core · Module 7
Recursion and the call stack
Functions that call themselves, and the stack frames that make it work.
Recursion is a function solving a problem by calling itself on smaller versions of it, and it works because every call gets its own stack frame. This module starts inside those frames, at the instructions a call really executes, then uses recursion trees to measure what recursive code costs, compares recursion with loops, and ends with backtracking: searching through choices one at a time and undoing them.
- 1How a function call worksPro — members onlyA call is a jump that remembers where to come back to. Arguments travel in registers, the return address goes on the stack, and a few instructions set up and tear down the frame.14 min
- 2Base cases and recursion treesPro — members onlyA recursive function needs a base case and a step that makes progress toward it. Drawing its calls as a tree tells you both its running time and its stack depth.14 min
- 3Recursion vs iterationPro — members onlyAny recursion can become a loop and any loop a recursion. Tail calls turn into loops with an accumulator, and general recursion into a loop over an explicit stack. Choose by clarity, depth and cost.13 min
- 4Backtracking basicsPro — members onlyBacktracking builds a solution one choice at a time, explores each choice recursively and undoes it afterwards. Pruning dead ends early is what makes it practical.15 min