4.16 Recursion

1. What makes a method recursive

A recursive method is a method that calls itself 4.16.A.1. Every recursive method contains at least one base case, which halts the recursion, and at least one recursive call 4.16.A.1. Recursion is another form of repetition, like a loop 4.16.A.1.

public static void countdown(int n)
{
    if (n == 0)                  // base case: stop
    {
        System.out.println("Liftoff!");
    }
    else
    {
        System.out.println(n);
        countdown(n - 1);        // recursive call
    }
}

countdown(3);

Output:

3
2
1
Liftoff!

Each call moves n one step closer to the base case. Scope note: writing recursive code is outside the scope of the AP® Computer Science A exam. You must be able to read recursive methods and determine the result of calling them 4.16.A.1.

2. Tracing a method that returns a value

Each recursive call has its own set of local variables, including its parameters 4.16.A.2. A call that is waiting for a deeper call to return stays “paused” with its own values. Java keeps these paused calls on the call stack.

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

System.out.println(sumDigits(4071));

Output:

12

Trace it in two directions. Going down, write each call. Coming back up, fill in each return value.

Call	n	Base case?	Returns
sumDigits(4071)	4071	no	1 + sumDigits(407) = 1 + 11 = 12
sumDigits(407)	407	no	7 + sumDigits(40) = 7 + 4 = 11
sumDigits(40)	40	no	0 + sumDigits(4) = 0 + 4 = 4
sumDigits(4)	4	yes	4

There are four calls and four different values of n alive at the same time. When sumDigits(4) returns, sumDigits(40) continues with its own n, which is still 40.

3. Before or after the recursive call

Where a statement sits relative to the recursive call decides when it runs. A statement before the call runs on the way down. A statement after the call waits until every deeper call has returned, so it runs on the way back up, in reverse order 4.16.A.2.

public static void echo(String word)
{
    if (word.length() > 0)
    {
        System.out.print(word.substring(0, 1));       // before the call
        echo(word.substring(1));
        System.out.print(word.substring(0, 1));       // after the call
    }
}

echo("abc");
System.out.println();

Output:

abccba

Step	What happens	Printed so far
1	echo("abc") prints a, calls echo("bc")	a
2	echo("bc") prints b, calls echo("c")	ab
3	echo("c") prints c, calls echo("")	abc
4	echo("") is the base case: does nothing, returns	abc
5	back in echo("c"): prints c	abcc
6	back in echo("bc"): prints b	abccb
7	back in echo("abc"): prints a	abccba

4. Parameters track progress, like a loop control variable

Parameter values capture the progress of a recursive process, much like the values of a loop control variable capture the progress of a loop 4.16.A.2. Some methods make more than one recursive call; draw a tree of calls and add the results from the bottom up.

public static int paths(int steps)
{
    if (steps <= 1)
    {
        return 1;
    }
    return paths(steps - 1) + paths(steps - 2);
}

System.out.println(paths(4));

Output:

5

Call tree for paths(4):

Call	Makes the calls	Returns
paths(4)	paths(3) and paths(2)	3 + 2 = 5
paths(3)	paths(2) and paths(1)	2 + 1 = 3
paths(2)	paths(1) and paths(0)	1 + 1 = 2
paths(1), paths(0)	base cases	1 each

In total paths(4) causes 9 calls, because paths(2) is computed twice and paths(1) three times.

5. Recursion and iteration are interchangeable

Any recursive solution can be replicated with an iterative approach (a loop), and any iterative solution can be written recursively 4.16.A.3. The parameter plays the role of the loop control variable, and the base case plays the role of the loop condition becoming false.

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

public static int powerLoop(int base, int exp)
{
    int result = 1;
    for (int i = exp; i > 0; i--)
    {
        result *= base;
    }
    return result;
}

System.out.println(powerRec(3, 4) + " " + powerLoop(3, 4));

Output:

81 81

Recursive version	Iterative version
parameter exp	loop control variable i
exp - 1 in the recursive call	i--
base case exp == 0	loop stops when i > 0 is false

6. No base case reached: StackOverflowError

If the recursive calls never reach a base case, every call waits on the call stack until Java runs out of room 4.16.A.1. The program stops with an error.

public static int halve(int n)
{
    if (n == 1)
    {
        return 0;
    }
    return 1 + halve(n / 2);
}

System.out.println(halve(8));
System.out.println(halve(0));

Output:

3
Exception in thread "main" java.lang.StackOverflowError

halve(8) reaches the base case after three recursive calls (n is 8, then 4, 2 and 1). But halve(0) calls halve(0) again and again, because 0 / 2 is 0 and the base case n == 1 is never true.