Overview
EasyBase case, recursive case, the call stack
Solve a big job by doing a tiny piece and asking a smaller copy of yourself to do the rest.
The idea
Every recursion needs a base case that stops it and a recursive case that moves toward the base. Each call gets its own frame on the stack; picture the tree of calls to reason about work done.
The trick
- If the recursion never reaches the base case, you get a stack overflow.
- Total work = number of nodes in the recursion tree.
Step 1 of 10. Recursion is when something uses itself. Like a countdown: to count down from 3, say 3, then count down from 2…
1/10
Optimal
timevariesspaceO(depth)
Stop, then shrink.
1function solve(state) {2 if (isBase(state)) return baseValue;3 return combine(solve(smaller(state)));4}Memory
- calls waiting
- —
Output
- calls waiting
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- reverse("abc")
- Output:
- "cba"
- Explanation:
- Trust reverse("bc") to return "cb", then put 'a' on the end. You only handle one step and the empty-string base case.
Example 2
- Input:
- depth of fib(5) recursion
- Output:
- 5 levels, 15 calls
- Explanation:
- The tree branches twice per level, which is exactly why the next chapter caches results instead.
Finished the walkthrough? Add it to your streak.