Unit 1 · Foundational
Solving a problem by defining a smaller version of itself. The unit is less about writing recursive code than about arguing that it terminates and that the recursive step actually covers the problem.
What a strong answer looks like
A strong Unit 1 answer names the base case, shows every call moves toward it, and states what the recursive step assumes.
Know
A base case stops the recursion. It must be reachable from every possible call, which is a stronger requirement than merely existing.
Apply
Write the base case first, then check that each recursive call strictly reduces the input toward it.
Watch out
A base case that exists but is unreachable for some inputs, such as testing equality when the input decreases by two.
Study move
Write a recursion whose base case is unreachable for odd inputs, then repair it.
Know
Each pending call occupies a stack frame, so recursion depth costs memory even when the code looks small.
Apply
State the recursion depth for a given input to reason about space, not only time.
Watch out
Assuming recursion is free. Depth proportional to input size means linear extra space.
Study move
Compare the space used by a recursive and an iterative sum over a list of length n.
Know
A recursive method is argued correct by assuming the recursive call works on a smaller input and showing the combination step is right.
Apply
Write the argument in two parts: base case correct, and recursive step correct given the assumption.
Watch out
Tracing one example and calling it a proof. A trace is evidence, not an argument.
Study move
Write the two-part correctness argument for a recursive tree height method.
Know
Some problems are naturally recursive because their structure is recursive, such as trees. Others are clearer as loops.
Apply
Choose recursion where the data is self-similar and iteration where progress is linear.
Watch out
Forcing recursion onto a simple accumulation, which adds stack cost for no clarity.
Study move
Convert a recursive list sum to iteration and say which reads better and why.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Write a recursive method returning the height of a binary tree, then give its base case, its recursive step, and its worst-case space cost.
