13.8: Recursive Methods
- Page ID
- 18822
Now that we have conditional statements, we can explore one of the most magical things a program can do: recursion. 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 zero, it displays the word “Blastoff”. Otherwise, it displays the number and then invokes itself, passing n - 1
as the argument. A method that invokes itself is called recursive.
What happens if we invoke countdown(3)
from main
?
The execution of countdown
begins with n == 3
, and since n
is not zero, it displays the value 3, and then invokes itself...
The execution of countdown
begins with n == 2
, and since n
is not zero, 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 zero, 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.
And then you’re back in main. So the total output looks like:
3 2 1 Blastoff!
As a second example, we’ll rewrite the methods newLine
and threeLine
from Section 4.3.
public static void newLine() { System.out.println(); } public static void threeLine() { newLine(); newLine(); newLine(); }
Although these methods work, they would not help if we wanted to display two newlines, or maybe 100. A better alternative would be:
public static void nLines(int n) { if (n > 0) { System.out.println(); nLines(n - 1); } }
This method takes an integer, n
, as a parameter and displays n
newlines. The structure is similar to countdown
. As long as n is greater than zero, it displays a newline and then invokes itself to display (n−1) additional newlines. The total number of newlines is 1 + (n − 1), which is just what we wanted: n.