4.16 RecursionRecursion: a method that calls itself

A recursive method is a method that calls itself. Every recursive method needs a base case, a condition where it stops and answers without calling itself again. Every recursive call must move toward the base case, usually by working on a smaller number or a shorter String. Without that, the calls never end.
?Wait, what happens when one method calls another?
Each call gets its own copy of the parameters and local variables. So when wave(3) calls wave(2), there are now two n's: the paused call's n is 3, and the new call's n is 2. Java keeps the paused calls on a stack and finishes them in reverse order, last called, first finished.
1public static void wave(int n)2{3 if (n == 0)14 {15 return;16 }17 System.out.print(n + " ");28 wave(n - 1);39 System.out.print(n + " ");410}11// in main12wave(3);
- line 3-6 Base case: stop, no more calls
- line 7 Runs on the way in, before the call
- line 8 Recursive call on a smaller value
- line 9 Runs on the way out, after the call returns
I thought about it. Show me
For a recursive method that returns a value, trace in two directions. Going down, write each call and what it's waiting for. At the base case you get a real answer. Then go back up, filling in each waiting call's return value from the one below it.
1public static int countX(String s)2{3 if (s.length() == 0)14 {15 return 0;16 }17 int rest = countX(s.substring(1));28 if (s.substring(0, 1).equals("x"))39 {310 return 1 + rest;311 }312 return rest;13}
- line 3-6 Base case: the empty String has no x
- line 7 Count the x's in everything after the first letter
- line 8-11 Then add 1 if the first letter is an x
?Wait, what does substring(1) give?
| call | first letter | waits for | returns |
|---|---|---|---|
| countX("axxbx") | a | countX("xxbx") | 0 + 3 = 3 |
| countX("xxbx") | x | countX("xbx") | 1 + 2 = 3 |
| countX("xbx") | x | countX("bx") | 1 + 1 = 2 |
| countX("bx") | b | countX("x") | 0 + 1 = 1 |
| countX("x") | x | countX("") | 1 + 0 = 1 |
| countX("") | nothing: base case | 0 |
Two more facts. If the base case is missing, or the calls never reach it, the method keeps calling itself until Java runs out of room for paused calls and throws a StackOverflowError. And anything you can do with recursion you can also do with a loop. Recursion just makes some problems, like searching and sorting in halves, much shorter to write.
What does mystery(7) return?
public static int mystery(int n)
{
if (n <= 1)
{
return 1;
}
return n * mystery(n - 2);
}- Going down: mystery(7) waits for 7 * mystery(5), which waits for 5 * mystery(3), which waits for 3 * mystery(1).
Why?
Each call subtracts 2, so it moves toward n <= 1. - mystery(1) is the base case: 1 <= 1, so it returns 1.
- Coming back up: mystery(3) returns 3 * 1 = 3. mystery(5) returns 5 * 3 = 15. mystery(7) returns 7 * 15 = 105.
Answer: 105
Stuck? Get a hint
- Write each call on its own line: mystery(7), mystery(5), and so on.
- Stop when n <= 1, and write the 1 it returns.
- Multiply your way back up: 3 * 1, then 5 * 3, then 7 * 15.
public static int f(int n)
{
if (n < 3)
{
return n;
}
return f(n - 1) + f(n - 3);
}- A5
- B3
- C8
- D2
Show the answer
A. The base case returns n when n < 3, so f(0) = 0, f(1) = 1, f(2) = 2. Build up: f(3) = f(2) + f(0) = 2, f(4) = f(3) + f(1) = 3, and f(5) = f(4) + f(2) = 3 + 2 = 5. The second choice is the trap: it's f(4), one level short.

On recursion questions, make a table with one row per call: the call, what it waits for, and what it returns. Fill the returns from the bottom up. Don't try to hold it all in your head; that's where points get lost.
- A recursive method calls itself. It needs a base case, and each call must move toward it.
- Each call has its own parameters and local variables. Paused calls finish in reverse order.
- Code before the recursive call runs on the way down; code after it runs on the way back up.
- Trace returns from the base case up. No base case: StackOverflowError.
- You trace recursion on the exam; you don't have to write it.