JAVA / CHAPTER 13
Recursion
AdvancedProve progress toward a base case and trace returned results.
By the end of this chapter
- Identify a base case
- Trace recursive calls and returns
- State input constraints
The idea
A recursive method solves a problem by calling itself on a smaller related problem. It needs both a base case and progress toward that case. For a nonnegative integer n, reducing n by one eventually reaches zero. A base case alone is insufficient if some allowed inputs move away from it. Document the valid domain and decide how to reject inputs outside it.
Each call has its own parameters and local variables. When a call returns, the waiting caller continues with that result. Draw a call chain downward and compute return values upward. Recursive solutions can be clear, but very deep chains consume stack space; a loop may be preferable when the input can be large.
public class Main {
static int sumTo(int n) {
if (n < 0) throw new IllegalArgumentException();
if (n == 0) return 0;
return n + sumTo(n - 1);
}
public static void main(String[] args) {
System.out.println(sumTo(4));
}
}10
The calls reach sumTo(0), then return zero, one, three, six, and ten as the waiting additions finish.
Try it yourself
Write a recursive method counting the occurrences of a character in an ASCII string by advancing an index.
Use your own editor for this exercise. Runnable challenges on CodeQuest are available for JavaScript, Python, and SQL.
CHECK YOUR UNDERSTANDING