AP Computer Science A · Unit 4 lecture · Part 12 of 14 · 10 min

4.16 RecursionRecursion: a method that calls itself

Mr. Thompkins
Recursion sounds like a magic trick, but it follows the same rules as every method call you've already traced. And on the AP exam you only have to trace it, never write it. Let's build a way to trace it every time.

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?
The caller pauses at that exact line. The called method runs with its own parameters and local variables, and when it returns, the caller picks up right where it paused. Recursion is the same, except the method being called is a fresh copy of the same method.

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);
  1. line 3-6 Base case: stop, no more calls
  2. line 7 Runs on the way in, before the call
  3. line 8 Recursive call on a smaller value
  4. line 9 Runs on the way out, after the call returns
output › 3 2 1 1 2 3
A print before the recursive call and another after it.
wave(3)wave(2)wave(1)wave(0)prints 3prints 2prints 1then prints 3then prints 2then prints 1base casereturns at oncedown: before the call. up: after it
Going down, each call prints before it calls. Coming back up, each paused call finishes its last line.
Pause and think
What does wave(2) print?
I thought about it. Show me
2 1 1 2. The first prints happen on the way down (2, then 1), wave(0) returns at once, and the second prints happen on the way back up, in reverse order (1, then 2).

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}
  1. line 3-6 Base case: the empty String has no x
  2. line 7 Count the x's in everything after the first letter
  3. line 8-11 Then add 1 if the first letter is an x
output › countX("axxbx") returns 3
Count the x's in a String by checking one letter and recursing on the rest.
?Wait, what does substring(1) give?
s.substring(1) is everything from index 1 to the end: "axxbx".substring(1) is "xxbx". On a one-letter String it gives the empty String "", which is how countX reaches its base case.
callfirst letterwaits forreturns
countX("axxbx")acountX("xxbx")0 + 3 = 3
countX("xxbx")xcountX("xbx")1 + 2 = 3
countX("xbx")xcountX("bx")1 + 1 = 2
countX("bx")bcountX("x")0 + 1 = 1
countX("x")xcountX("")1 + 0 = 1
countX("")nothing: base case0
Write the calls going down, then fill in the returns going up, starting from the highlighted base case.

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.

Trace the returns

What does mystery(7) return?

public static int mystery(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    return n * mystery(n - 2);
}
  1. 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.
  2. mystery(1) is the base case: 1 <= 1, so it returns 1.
  3. 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
  1. Write each call on its own line: mystery(7), mystery(5), and so on.
  2. Stop when n <= 1, and write the 1 it returns.
  3. Multiply your way back up: 3 * 1, then 5 * 3, then 7 * 15.
Check yourself
What does f(5) return?
public static int f(int n)
{
    if (n < 3)
    {
        return n;
    }
    return f(n - 1) + f(n - 3);
}
  1. A5
  2. B3
  3. C8
  4. 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.

Exam tip from Mr. T

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.