Recursion

Every way you have repeated code so far has used a loop. To count down for a rocket launch, you would write a while loop like this one from Topic 2.7:

public class LaunchLoop
{
    public static void main(String[] args)
    {
        int n = 3;
        while (n > 0)
        {
            System.out.println(n);
            n--;
        }
        System.out.println("Liftoff!");
    }
}

3
2
1
Liftoff!

There is a second way to get repetition, and it uses nothing but methods and if. Think about how you would explain a countdown to a friend without saying “repeat”. You might say: “To count down from 3, say 3, then count down from 2.” And to count down from 2? “Say 2, then count down from 1.” Each instruction hands a smaller copy of the same job to the next step, until the job is so small (count down from 0) that you just shout “Liftoff!” and stop.

Java lets a method work the same way. From Topic 3.5 you know a method can call another method. Nothing stops a method from calling itself. A recursive method is a method that calls itself, and the call inside its own body is the recursive call. Using recursive methods to repeat work is called recursion.

public class LaunchRecursive
{
    public static void countdown(int n)
    {
        if (n == 0)
        {
            System.out.println("Liftoff!");
        }
        else
        {
            System.out.println(n);
            countdown(n - 1);
        }
    }

    public static void main(String[] args)
    {
        countdown(3);
    }
}

3
2
1
Liftoff!

The argument decides how many times the work repeats, just as the starting value of n decided it in the loop. Change only the calls in main:

public class LaunchStarts
{
    public static void countdown(int n)
    {
        if (n == 0)
        {
            System.out.println("Liftoff!");
        }
        else
        {
            System.out.println(n);
            countdown(n - 1);
        }
    }

    public static void main(String[] args)
    {
        countdown(5);
        countdown(0);
    }
}

5
4
3
2
1
Liftoff!
Liftoff!

On the AP exam you will be asked to read and trace recursive methods, not to write them. Every question in this guide practices reading: predicting output, finding return values, and spotting why a call never stops.

public class HopTrace
{
    public static void hop(int n)
    {
        if (n < 3)
        {
            System.out.println("Landed at " + n);
        }
        else
        {
            System.out.println("Hop from " + n);
            hop(n - 3);
        }
    }

    public static void main(String[] args)
    {
        hop(10);
    }
}

Hop from 10
Hop from 7
Hop from 4
Landed at 1

public class TickTock
{
    public static void tick(int count)
    {
        if (count > 0)
        {
            System.out.println("tick");
            tick(count - 1);
        }
    }

    public static void main(String[] args)
    {
        tick(4);
    }
}

In LaunchRecursive.java, what would happen if the if were not there and the method always called itself? A loop with a condition that never becomes false runs forever (Topic 2.7). A recursive method needs the same kind of exit, and it has a name.

Every recursive method has two kinds of paths through its body:

• A base case is a path that finishes without making a recursive call. It is the “small enough to just do it” situation, and reaching it halts the recursion. Every recursive method needs at least one.
• A recursive case is a path that makes at least one recursive call. Every recursive method has at least one of these too; otherwise it would not be recursive.

For recursion to stop, each recursive call must pass an argument that is closer to the base case than the current one. countdown(n - 1) moves n one step toward 0 every time.

A base case does not have to print or return anything. In TickTock.java (question 2), the base case is the call where count > 0 is false: the method skips its block and simply ends. “Do nothing and stop” is a perfectly good base case.

public class HalveRecursive
{
    public static void halve(int n)
    {
        if (n == 0)
        {
            System.out.println("Reached 0");
        }
        else
        {
            System.out.println(n);
            halve(n / 2);
        }
    }

    public static void main(String[] args)
    {
        halve(10);
    }
}

10
5
2
1
Reached 0

public class NoBaseCase
{
    public static void countdown(int n)
    {
        System.out.println(n);
        countdown(n - 1);
    }

    public static void main(String[] args)
    {
        countdown(3);
    }
}

Exception in thread "main" java.lang.StackOverflowError

public class LapCounter
{
    public static void laps(int remaining)
    {
        if (remaining == 0)
        {
            System.out.println("Finished");
        }
        else
        {
            System.out.println(remaining + " to go");
            laps(remaining - 2);
        }
    }

    public static void main(String[] args)
    {
        laps(6);
        laps(5);
    }
}

        if (remaining <= 0)

public class ClimbCheck
{
    public static void climb(int step)
    {
        if (step == 10)
        {
            System.out.println("Top");
        }
        else
        {
            climb(step + 1);
        }
    }

    public static void main(String[] args)
    {
        climb(4);
        climb(10);
        climb(-3);
        climb(12);
    }
}

So far every recursive call has been the last thing its method did. What if there is code after the recursive call? To trace it you need to answer a question you may already be wondering about: when countdown(3) calls countdown(2), the new call sets n to 2. Did the first call’s n just get overwritten?

It did not. Recall from Topic 3.5 that every call to a method gets fresh parameters, filled with copies of the arguments, and from Topic 3.8 that parameters and local variables exist only while their call is running. Those rules do not change when the method calling is the same method. Each recursive call gets its own n and its own copy of every local variable, completely separate from the n of the call that is waiting for it.

A good picture is a stack of sticky notes. Starting a call puts a new note on top, with that call’s variables written on it. Only the top note is being worked on; the notes underneath are calls that are paused at their recursive call. When the top call finishes, its note is thrown away and the call just below picks up exactly where it paused, with its own variables untouched. This stack of waiting calls is the call stack from 4.16.2. (Unlike sticky notes, you never write or erase the notes yourself; Java does it on every call and return.)

public class CountUp
{
    public static void countUp(int n)
    {
        if (n == 0)
        {
            System.out.println("Start");
        }
        else
        {
            countUp(n - 1);
            System.out.println(n);
        }
    }

    public static void main(String[] args)
    {
        countUp(3);
    }
}

Start
1
2
3

countUp(3)             n = 3, pauses at line 11
  countUp(2)           n = 2, pauses at line 11
    countUp(1)         n = 1, pauses at line 11
      countUp(0)       n = 0, base case: prints Start
    countUp(1) resumes at line 12: prints its n, 1
  countUp(2) resumes at line 12: prints its n, 2
countUp(3) resumes at line 12: prints its n, 3

Local variables declared inside the method behave the same way as parameters. In the next example, each call computes its own doubled before the recursive call and uses it again afterward.

public class DownAndUp
{
    public static void echo(int n)
    {
        int doubled = n * 2;
        if (n == 0)
        {
            System.out.println("Bottom");
        }
        else
        {
            System.out.println("Down " + doubled);
            echo(n - 1);
            System.out.println("Up " + doubled);
        }
    }

    public static void main(String[] args)
    {
        echo(2);
    }
}

Down 4
Down 2
Bottom
Up 2
Up 4

public class ShrinkTrace
{
    public static void shrink(int n)
    {
        if (n > 0)
        {
            n = n - 1;
            shrink(n);
            System.out.println(n);
        }
    }

    public static void main(String[] args)
    {
        shrink(3);
    }
}

0
1
2

Printing is one way a recursive method can produce results. More often, a recursive method returns a value. Suppose you want the total of 1 + 2 + … + n. You could add the numbers with a loop. But notice that the total up to 4 is just 4 plus the total up to 3, and the total up to 3 is 3 plus the total up to 2, and so on, down to the total up to 1, which is simply 1. Each total is described using a smaller total: that is a recursive description.

From Topic 3.5, a non-void method’s call is replaced by the value it returns, and the caller continues the expression with that value. In a recursive method, the caller is just an earlier call to the same method, waiting in the middle of an expression for the answer.

public class SumTo
{
    public static int sumTo(int n)
    {
        if (n == 1)
        {
            return 1;
        }
        return n + sumTo(n - 1);
    }

    public static void main(String[] args)
    {
        System.out.println(sumTo(4));
    }
}

10

sumTo(4) = 4 + sumTo(3)
               sumTo(3) = 3 + sumTo(2)
                              sumTo(2) = 2 + sumTo(1)
                                             sumTo(1) = 1      base case
                              sumTo(2) = 2 + 1 = 3
               sumTo(3) = 3 + 3 = 6
sumTo(4) = 4 + 6 = 10

A method can have more than one base case. This one answers a yes-or-no question by stepping down by 3, and it needs one base case for “landed exactly on 0” and another for “went past 0”.

public class MultipleOfThree
{
    public static boolean isMultipleOfThree(int n)
    {
        if (n == 0)
        {
            return true;
        }
        if (n < 0)
        {
            return false;
        }
        return isMultipleOfThree(n - 3);
    }

    public static void main(String[] args)
    {
        System.out.println(isMultipleOfThree(9));
        System.out.println(isMultipleOfThree(7));
    }
}

true
false

public class SumToIgnored
{
    public static int sumTo(int n)
    {
        if (n == 1)
        {
            return 1;
        }
        sumTo(n - 1);
        return n;
    }

    public static void main(String[] args)
    {
        System.out.println(sumTo(4));
    }
}

4

public class ProductOdd
{
    public static int product(int n)
    {
        if (n <= 1)
        {
            return 1;
        }
        return n * product(n - 2);
    }

    public static void main(String[] args)
    {
        System.out.println(product(7));
    }
}

105

product(7) = 7 * product(5)
product(5) = 5 * product(3)
product(3) = 3 * product(1)
product(1) = 1                 base case (1 <= 1)
product(3) = 3 * 1  = 3
product(5) = 5 * 3  = 15
product(7) = 7 * 15 = 105

When you trace a loop, the loop control variable tells you where you are: in for (int i = 3; i <= 6; i++), seeing i == 5 means the loop is on its third pass and has two values left (Topics 2.7 and 2.8). A recursive method has no loop control variable. So what plays that role?

The parameters do. Each call receives its own parameter values, and those values describe how far the process has come. In countdown, a call with n == 1 is one step from the base case, just as n == 1 in LaunchLoop.java is one pass from the end of the loop. The difference is where the value lives: a loop changes one variable over and over, while recursion gives each call a new parameter that holds the next value.

The match is easiest to see when a recursive method carries everything a loop would track, including a running total, in its parameters.

public class AddRange
{
    public static int addLoop(int start, int stop)
    {
        int total = 0;
        for (int i = start; i <= stop; i++)
        {
            total = total + i;
        }
        return total;
    }

    public static int addRecursive(int i, int stop, int total)
    {
        if (i > stop)
        {
            return total;
        }
        return addRecursive(i + 1, stop, total + i);
    }

    public static void main(String[] args)
    {
        System.out.println(addLoop(3, 6));
        System.out.println(addRecursive(3, 6, 0));
    }
}

18
18

Parameters can track progress in any quantity, not just a counter. Here the parameter balance records how far a savings account has grown.

public class YearsToGoal
{
    public static int yearsToGoal(int balance, int goal)
    {
        if (balance >= goal)
        {
            return 0;
        }
        return 1 + yearsToGoal(balance + balance / 10, goal);
    }

    public static void main(String[] args)
    {
        System.out.println(yearsToGoal(1000, 1300));
        System.out.println(yearsToGoal(1500, 1300));
    }
}

3
0

public class AddRangeStuck
{
    public static int addRecursive(int i, int stop, int total)
    {
        if (i > stop)
        {
            return total;
        }
        return addRecursive(i, stop, total + i);
    }

    public static void main(String[] args)
    {
        System.out.println(addRecursive(3, 6, 0));
    }
}

public class Halvings
{
    public static int halvings(int n, int count)
    {
        if (n <= 1)
        {
            return count;
        }
        return halvings(n / 2, count + 1);
    }

    public static void main(String[] args)
    {
        System.out.println(halvings(40, 0));
    }
}

5

You have now seen several jobs done both ways: the countdown in 4.16.1 and the range sum in 4.16.5. That was no coincidence. Any recursive solution can be rewritten as an iterative one (one that repeats with a loop), and any iterative solution can be rewritten recursively. Neither tool can solve a problem the other cannot. Programmers choose whichever version is easier to read and reason about for the problem at hand.

To match the two versions, line up their parts:

public class DigitSum
{
    public static int digitSumRecursive(int n)
    {
        if (n < 10)
        {
            return n;
        }
        return n % 10 + digitSumRecursive(n / 10);
    }

    public static int digitSumLoop(int n)
    {
        int sum = 0;
        while (n > 0)
        {
            sum = sum + n % 10;
            n = n / 10;
        }
        return sum;
    }

    public static void main(String[] args)
    {
        System.out.println(digitSumRecursive(4721));
        System.out.println(digitSumLoop(4721));
        System.out.println(digitSumRecursive(7));
        System.out.println(digitSumLoop(7));
    }
}

14
14
7
7

The translation works in the other direction too. Start from a loop you might write yourself and look at its recursive twin.

public class PowerBothWays
{
    public static int powerLoop(int base, int exponent)
    {
        int result = 1;
        for (int count = exponent; count > 0; count--)
        {
            result = result * base;
        }
        return result;
    }

    public static int powerRecursive(int base, int exponent)
    {
        if (exponent == 0)
        {
            return 1;
        }
        return base * powerRecursive(base, exponent - 1);
    }

    public static void main(String[] args)
    {
        System.out.println(powerLoop(2, 5));
        System.out.println(powerRecursive(2, 5));
        System.out.println(powerLoop(3, 4));
        System.out.println(powerRecursive(3, 4));
    }
}

32
32
81
81

The two versions differ in one practical way you have already seen. The recursive version keeps a waiting call on the call stack for every step, so a recursive process with a very large number of steps, or with no base case, can end in StackOverflowError. A loop uses the same few variables on every pass. The results of a correct recursive version and a correct loop version are the same.

public class DigitSumLoopBug
{
    public static int digitSumLoop(int n)
    {
        int sum = 0;
        while (n >= 10)
        {
            sum = sum + n % 10;
            n = n / 10;
        }
        return sum;
    }

    public static void main(String[] args)
    {
        System.out.println(digitSumLoop(4721));
    }
}

10

public static int sumEveryOther(int n)
{
    if (n <= 0)
    {
        return 0;
    }
    return n + sumEveryOther(n - 2);
}

A staircase has n steps, and you climb by taking either 1 step or 2 steps at a time. How many different ways can you reach the top? For 3 steps there are three ways: 1+1+1, 1+2, and 2+1. Here is a recursive way to think about it: your first move is either 1 step, leaving n - 1 steps to climb, or 2 steps, leaving n - 2. So the number of ways for n steps is the ways for n - 1 plus the ways for n - 2. A staircase of 0 or 1 steps has exactly 1 way.

This method uses every idea in the chapter, plus one new twist: the recursive case makes two recursive calls. Before reading the trace, predict ways(4).

public class StairWays
{
    public static int ways(int n)
    {
        if (n <= 1)
        {
            return 1;
        }
        return ways(n - 1) + ways(n - 2);
    }

    public static int waysLoop(int n)
    {
        int before = 1;
        int current = 1;
        for (int step = 2; step <= n; step++)
        {
            int next = current + before;
            before = current;
            current = next;
        }
        return current;
    }

    public static void main(String[] args)
    {
        System.out.println(ways(4));
        System.out.println(waysLoop(4));
        System.out.println(ways(6));
        System.out.println(waysLoop(6));
    }
}

5
5
13
13

ways(4)
  ways(3)
    ways(2)
      ways(1) returns 1       base case
      ways(0) returns 1       base case
    ways(2) returns 1 + 1 = 2
    ways(1) returns 1         base case
  ways(3) returns 2 + 1 = 3
  ways(2)
    ways(1) returns 1         base case
    ways(0) returns 1         base case
  ways(2) returns 1 + 1 = 2
ways(4) returns 3 + 2 = 5

• A recursive method calls itself. It needs at least one base case, which finishes without calling again, and at least one recursive call. Recursion is another way to repeat work.
• Each recursive call must move its arguments closer to a base case. If the base case is missing or can be skipped over, the waiting calls pile up and the program crashes with StackOverflowError.
• Every call has its own parameters and local variables. A call that makes a recursive call waits, then resumes right after it with its own values unchanged, so code after a recursive call runs in reverse order of the calls.
• A recursive method that returns a value builds its answer on the way back: each call combines its own work with the value its recursive call returns.
• Parameter values show the progress of a recursive process, just as the loop control variable shows the progress of a loop.
• Any recursive solution can be rewritten with a loop, and any loop solution can be rewritten with recursion.

public class FoldCalls
{
    public static int fold(int n)
    {
        if (n <= 2)
        {
            return n;
        }
        return fold(n - 2) + 1;
    }

    public static void main(String[] args)
    {
        System.out.println(fold(7));
    }
}

public class PatternTrace
{
    public static void pattern(int n)
    {
        if (n <= 0)
        {
            System.out.println("|");
        }
        else
        {
            System.out.println("<" + n);
            pattern(n - 2);
            System.out.println(n + ">");
        }
    }

    public static void main(String[] args)
    {
        pattern(5);
    }
}

<5
<3
<1
|
1>
3>
5>

pattern(5)   prints <5, then calls pattern(3) and waits
  pattern(3)   prints <3, then calls pattern(1) and waits
    pattern(1)   prints <1, then calls pattern(-1) and waits
      pattern(-1)   -1 <= 0: base case, prints |
    pattern(1) resumes: prints 1>
  pattern(3) resumes: prints 3>
pattern(5) resumes: prints 5>

public class BinaryConvert
{
    public static int convert(int n)
    {
        if (n < 2)
        {
            return n;
        }
        return convert(n / 2) * 10 + n % 2;
    }

    public static void main(String[] args)
    {
        System.out.println(convert(11));
    }
}

1011

public class DrainCheck
{
    public static void drain(int n)
    {
        if (n == 0)
        {
            System.out.println("Empty");
        }
        else
        {
            drain(n - 4);
        }
    }

    public static void main(String[] args)
    {
        drain(8);
        drain(0);
        drain(6);
    }
}

public class FactorialBug
{
    public static int factorial(int n)
    {
        if (n == 1)
        {
            return 0;
        }
        return n * factorial(n - 1);
    }

    public static void main(String[] args)
    {
        System.out.println(factorial(4));
    }
}

            return 1;

public class ReverseDigits
{
    public static int reverseDigits(int n, int built)
    {
        if (n == 0)
        {
            return built;
        }
        return reverseDigits(n / 10, built * 10 + n % 10);
    }

    public static void main(String[] args)
    {
        System.out.println(reverseDigits(504, 0));
    }
}

405

public class CountCalls
{
    public static int count(int n)
    {
        if (n <= 1)
        {
            return 1;
        }
        return count(n - 1) + count(n - 2) + 1;
    }

    public static void main(String[] args)
    {
        System.out.println(count(4));
    }
}

• I can explain what makes a method recursive and why recursion is a form of repetition. Reread
• I can point out the base case and the recursive call, and decide which starting values reach the base case. Reread
• I can explain what causes a StackOverflowError in a recursive method. Reread
• I can trace output that comes before and after a recursive call, keeping each call’s own variables separate. Reread
• I can find the value a recursive method returns by working back up from the base case. Reread
• I can use parameter values to describe how far a recursive process has progressed. Reread
• I can match a recursive method with a loop that produces the same results. Reread