Card 08/ 08
Recap: Recursion
A reachable base case, a smaller input, work on both sides of the call, and a depth limit.
Recursion comes down to the seven ideas below, each listed with the card that covers it.
| The idea | Where |
|---|---|
| A recursive function has a base case it answers directly and a recursive case that calls itself on a smaller input | Recursion: A Function That Calls Itself on a Smaller Input |
| Every call gets a frame on the call stack, and a recursion n calls deep holds n + 1 frames at once | Recursion: A Function That Calls Itself on a Smaller Input |
| Work before the recursive call runs on the way down; work after it runs on the way back up, in reverse order | Trace a Recursive Call Through the Call Stack |
| Write a recursion by naming the smallest input, the smaller input, and how to combine; halving gives O(log n) calls | Write a Recursive Function From Its Definition |
| A structure made of smaller copies of itself, such as folders in folders, is counted by recursing into each copy | Recursion Example: Counting Files in Nested Folders |
A missing or unreachable base case fills the stack: RecursionError, StackOverflowError or RangeError | A Base Case the Recursion Never Reaches |
| A loop with an explicit stack replaces the call stack, and none of the three languages removes tail calls | Recursive and Explicit-Stack Folder Counts in Python, Java and TypeScript |
Each part of a recursive function has one job, and a characteristic way of going wrong. The second table pairs them, with the check that catches each mistake before the program runs. Most failures come from the base case or the smaller input; the last row is about the input rather than the code. Recursion is the right form when the definition is recursive and the depth stays small, and that last row is the one that decides between it and a loop.
| Part | Must | Goes wrong when | Check |
|---|---|---|---|
| Base case | Answer without calling again | It is missing, or the steps jump past it | Every input reaches it, including the smallest allowed |
| Smaller input | Move strictly closer to the base case | The input stays the same size or overshoots | Each call's input is smaller by a measure that ends at the base case |
| Combine | Turn the smaller answer into the larger one | Work after the call is forgotten when tracing | Trace both halves of the body, down and back up |
| Depth | Stay within the call stack's room | The input decides the depth, and it can be large | Use a loop with an explicit stack when depth grows with the input |
Together they let you write a recursive function from its definition, predict its output by tracing the stack, find a base case it will never reach, and rewrite it as a loop when its depth could outgrow the stack.
← → move through sections and cards