WebReference.com - Part 3 of chapter 5 from Beginning Java 2 SDK 1.4 Edition, Wrox Press Ltd (5/5)

[previous]

Beginning Java 2 SDK 1.4 Edition

Recursion

The methods you have seen so far have been called from within other methods, but a method can also call itself--something referred to as recursion. Clearly you must include some logic in a recursive method so that it will eventually stop calling itself. We can see how this might be done with a simple example.

We can write a method that will calculate integer powers of a variable, in other words, evaluate xⁿ, or x*x...*x where x is multiplied by itself n times. We can use the fact that we can obtain xⁿ by multiplying x^n-1 by x. To put this in terms of a specific example, we can calculate 2⁴ as 2³ multiplied by 2, and we can get 2³ by multiplying 2² by 2, and 2² is produced by multiplying 2¹, which is 2 of course, by 2.

Try It Out--Calculating Powers

Here is the complete program including the recursive method, power():

public class PowerCalc {
  public static void main(String[] args) {
    double x = 5.0;
    System.out.println(x + " to the power 4 is " + power(x,4));
    System.out.println("7.5 to the power 5 is " + power(7.5,5));
    System.out.println("7.5 to the power 0 is " + power(7.5,0));
    System.out.println("10 to the power -2 is " + power(10,-2));
  }
  // Raise x to the power n
  static double power(double x, int n) {
    if(n > 1)
      return x*power(x, n-1);    // Recursive call
    else if(n < 0)
      return 1.0/power(x, -n);   // Negative power of x
    else
      return n == 0 ? 1.0 : x;   // When n is 0 return 1, otherwise x
  }
}

This program will produce the output:

5.0 to the power 4 is 625.0
7.5 to the power 5 is 23730.46875
7.5 to the power 0 is 1.0
10 to the power -2 is 0.01

How It Works

The method power() has two parameters, the value x and the power n. The method performs four different actions, depending on the value of n:

Just to make sure the process is clear we can work through the sequence of events as they occur in the calculation of 5⁴.

Power(5.0, 4) {
  if(n > 1)
     return 5.0*power(5.0, 4-1);
  ...
}

Power(5.0, 3) {
  if(n > 1)
     return 5.0*power(5.0, 3-1);
  ...
}

Power(5.0, 2) {
  if(n > 1)
     return 5.0*power(5.0, 2-1);
  ...
}

Power(5.0, 1) {
  if(n > 1)
  ...
  else
    return 5.0;
}

Power(5.0, 2) {
  if(n>1)
  ...
  else
    return 5.0*5.0;
}

Power(5.0, 3) {
  if(n>1)
  ...
  else
    return 5.0*25.0;
}

Power(5.0, 4) {
  if(n > 1)
  ...
  else
    return 5.0*125.0;
}

You can see from this that the method power() is called four times in all. The calls cascade down through four levels until the value of n is such that it allows a value to be returned. The return values ripple up through the levels until we are eventually back at the top, and 625.0 is returned to the original calling point.

As a rule, you should only use recursion where there are evident advantages in the approach, as there is quite of lot of overhead in recursive method calls. This particular example could be more easily programmed as a loop and it would execute much more efficiently. One example of where recursion can be applied very effectively is in the handling of data structures such as trees. Unfortunately these don't make convenient illustrations of how recursion works at this stage of the learning curve, because of their complexity.

Before we can dig deeper into classes, we need to take an apparent detour to understand what a package is in Java. [To be continued in part 4. -Ed]

[previous]

Created: July 16, 2002
Revised: July 16, 2002

URL: https://webreference.com/programming/java/beginning/chap5/3/5.html