Recursion feels mysterious until students learn to separate two ideas: what one method call is responsible for, and when the chain of calls should stop. In Advanced Topics in CS, recursion is not just a syntax trick. It is a way to describe problems that shrink into smaller versions of themselves.
Start with the contract
Before tracing recursive code, write down what the method is supposed to return for one input. If the method counts, what exactly is being counted? If it searches, what exactly counts as success?
Base cases are not optional
The base case is the input where the answer is known without another recursive call. A weak base case often causes infinite recursion, stack overflow, or an answer that is off by one.
public static int sumDigits(int n)
{
if (n < 10)
return n;
return n % 10 + sumDigits(n / 10);
}The base case handles one digit. The recursive step removes the last digit and asks for the sum of the remaining digits.
Trace stack frames, not just values
Students often try to trace recursion like a loop. A better approach is to write each call on a separate line, then resolve the calls from the bottom back up.
Common mistakes
- Forgetting to make the input smaller.
- Writing a base case that does not cover the smallest valid input.
- Changing a parameter after the recursive call instead of before it.
- Returning too early before all recursive work is combined.
Practice idea
Pick one recursive method and trace it with three inputs: the smallest input, a medium input, and an input that triggers multiple calls. This builds the habit of checking whether the method stops and whether the returned values combine correctly.