Unit 7: Recursion
A function that calls itself, traced frame by frame on the call stack, where it shines, where it explodes, and how memoization tames it.
6 topics · 21 questions
Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.
Base Case and Recursive Case
- How it worksHow does a factorial function reduce n down to a base case of 0 before any multiplication happens?
- Worked exampleTrace def factorial(n): return 1 if n == 0 else n·factorial(n - 1) called as factorial(4).
- Common mistakeWhy doesn't a recursive function need a loop anywhere in its code to repeat work?
Your turn1 of 2
A recursive function sum_to(n) returns 0 if n == 0, else n + sum_to(n - 1). What does sum_to(140) return?Tracing Recursion on the Call Stack
- How it worksHow does each recursive call to factorial push a new frame that waits for the one below it to return?
- Worked exampleTrace the call stack growing to four frames for factorial(3) and unwinding as each call returns.
- Going furtherWhat happens to the call stack when factorial(n) is called with n that never reaches its base case?
Your turn1 of 2
Computing factorial(14) recursively pushes one new stack frame per call until it reaches the base case. How many total stack frames exist at the deepest point, counting the base case's own frame?Stack Overflow from Infinite Recursion
- How it worksHow does every unfinished recursive call pile a new frame onto the stack until it runs out of room?
- Worked exampleTrace def countdown(n): return countdown(n - 1) called as countdown(5) and find why it never returns.
- Common mistakeWhy isn't a stack overflow just the program running very slowly instead of crashing outright?
- Going furtherWhat happens to the maximum recursion depth once a language's default stack size is increased?
Your turn1 of 2
A recursive function pushes one new frame per call, and a stack overflow occurs once the depth reaches 3634. If the function starts at depth 324 and never reaches its base case, how many more calls are needed to reach the overflow limit?Tree Recursion: Naive Fibonacci
- How it worksHow does fib(n) branch into fib(n-1) and fib(n-2), building a tree of calls instead of a single chain?
- Worked exampleTrace the call tree for fib(5) built from fib(n) = fib(n-1) + fib(n-2) and count how often fib(2) recomputes.
- Common mistakeWhy isn't recursion always slower than a loop just because it calls itself?
- Going furtherWhat happens to the size of the Fibonacci call tree as n climbs from 10 to 40?
Your turn1 of 2
Naive recursive fib(n) branches into two calls at every step, roughly doubling the call count each time n increases by 1. If fib(22) makes about 6493 calls, about how many calls does fib(22 + 1) make?Memoization: Caching Recursive Results
- How it worksHow does a cache dictionary let memoized fib(n) return instantly on a repeated call instead of recomputing?
- Worked exampleTrace memoized fib(5) and watch fib(2) collapse into one cache hit instead of being recomputed three times.
- Common mistakeWhy doesn't memoization change what answer a recursive function returns, only how long it takes?
- Ties togetherHow does the memoized Fibonacci call tree collapse compared with the exploding tree of the naive version?
Your turn1 of 2
A memoized fib(n) function computes each distinct subproblem exactly once and caches it. For fib(70), how many distinct subproblems, fib(0) through fib(n), get computed in total?Recursion Versus Iteration and the Cost of the Stack
- How it worksHow does an iterative loop reuse one stack frame while recursion keeps stacking a new frame per call?
- Worked exampleTrace the space used by recursive sum_to(100000) versus an iterative version with one running total.
- Going furtherWhat changes about the stack cost once a recursive function is rewritten in tail-recursive form?
Your turn1 of 2
An iterative loop reuses a single stack frame across all its passes, while a recursive version pushes one new frame per call. For summing 69645 numbers, how many stack frames does the recursive version use at its deepest point?