The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Home Conditionals, Graphics and Recursion Recursion
See also: More Recursion, A Fractal Mickey Mouse 
del.icio.us Reddit Facebook StumbleUpon MySpace Twitter Search the VIAS Library  |  Index

Recursion

I mentioned in the last chapter that it is legal for one method to call another, and we have seen several examples of that. I neglected to mention that it is also legal for a method to invoke itself. It may not be obvious why that is a good thing, but it turns out to be one of the most magical and interesting things a program can do.

For example, look at the following method:

  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 and it takes a single integer as a parameter. If the parameter is zero, it prints the word "Blastoff." Otherwise, it prints the number and then invokes a method named countdown---itself---passing n-1 as an argument.

What happens if we invoke this method, in main, like this:

    countdown (3);

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

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

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

The execution of countdown begins with n=0, and since n is zero, it prints 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 (what a trip). So the total output looks like:

3
2
1
Blastoff!

As a second example, let's look again at the methods newLine and threeLine.

  public static void newLine () {
    System.out.println ("");
  }

  public static void threeLine () {
    newLine ();  newLine ();  newLine ();
  }

Although these work, they would not be much help if I wanted to print 2 newlines, or 106. A better alternative would be

  public static void nLines (int n) {
    if (n > 0) {
      System.out.println ("");
      nLines (n-1);
    }
  }

This program is very similar; as long as n is greater than zero, it prints one newline, and then invokes itself to print n-1 additional newlines. Thus, the total number of newlines that get printed is 1 + (n-1), which usually comes out to roughly n.

The process of a method invoking itself is called recursion, and such methods are said to be recursive.
Home Conditionals, Graphics and Recursion Recursion

Last Update: 2011-01-24