TOPIC 4.16 · STUDY
Recursion
A recursive method solves a problem by calling itself on a smaller case. A base case stops the chain with a return or a print and no further call. Statements before the recursive call run on the way down; statements after it run on the way back.
4.16.A
How a recursive method works
A recursive method calls itself, but each call must pass a smaller version of the problem. Typical shrinks are n - 1, n / 10, or a shorter substring. The chain of calls builds until a base case decides the work is finished.
The base case returns a value or prints something without making another recursive call. Without that stop rule, every call would spawn another call and the process would never end.
public static void signal(int n)
{
if (n == 0)
{
System.out.print("done");
}
else
{
System.out.print(n);
signal(n - 1);
}
}
// signal(3) prints 321done
Work placed before the recursive call runs on the way down, while new calls are still being made. In signal, print(n) happens first, so 3 appears, then 2, then 1, and only then does the base case print done.
public static void climb(int n)
{
if (n == 0)
{
return;
}
climb(n - 1);
System.out.print(n);
}
// climb(3) prints 123
Work placed after the recursive call runs on the way back, after deeper calls finish. climb waits for climb(n - 1) to return before printing, so the values appear as 1, then 2, then 3.
Each call waits for the smaller call below it. The base case ends the chain, then unfinished work after each call can run on the way back up.
Recursive methods can also return a value built from the smaller result. A product helper multiplies n by the product of the values below it until a base case returns 1.
public static int pack(int n)
{
if (n <= 1)
{
return 1;
}
return n * pack(n - 1);
}
// pack(4) returns 24
// calls: pack(4), pack(3), pack(2), pack(1)
pack(4) waits for pack(3), which waits for pack(2), which waits for pack(1). The base case returns 1, then each caller multiplies on the way back: 2 * 1, then 3 * 2, then 4 * 6, so the original call returns 24.
Key points
- A recursive method calls itself with a smaller problem.
- A base case stops the calls and returns or prints without another call.
- Work before the recursive call happens on the way down.
- Work after the recursive call happens on the way back.
- Returned values can combine the current argument with the result from the smaller call.
Without a base case the calls do not stop.