Think Java, 2nd Edition

Chapter 8. Recursive Methods

Up to this point, we’ve been using while and for loops whenever we’ve needed to repeat something. Methods that use iteration are called iterative. They are straight-forward, but sometimes more-elegant solutions exist.

In this chapter, we explore one of the most magical things that a method can do: invoke itself to solve a smaller version of the same problem. A method that invokes itself is called recursive.

Recursive Void Methods

Consider the following example:

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

The name of the method is countdown; it takes a single integer as a parameter. If the parameter is 0, it displays the word Blastoff. Otherwise, it displays the number and then invokes itself, passing n - 1 as the argument.

What happens if we invoke countdown(3) from main?

The execution of countdown begins with n == 3, and since n is not 0, it displays the value 3, and then invokes itself...

The execution of countdown begins with n == 2, and since n is not 0, it displays the value 2, and then invokes itself...

The execution of countdown begins with n == 1, and since n is not zero, it displays the value 1, and then invokes itself...

The execution of countdown begins with n == 0, and since n is 0, it displays the word Blastoff! and then returns.

The countdown that got n == 1 returns.

The countdown that got n == 2 returns.

The countdown that got n == 3 returns. ...