Java Tutorial

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 xn, or x*x...*x where x is multiplied by itself n times. We can use the fact that we can obtain xn by multiplying xn-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:

n>1	A recursive call to power() is made with n reduced by 1, and the value returned is multiplied by x. This is effectively calculating xⁿ as x times x^n-1.
n<0	x-n is equivalent to 1/xn so this is the expression for the return value. This involves a recursive call to power() with the sign of n reversed.
n=0	x0 is defined as 1, so this is the value returned.
n=1	x1 is x, so x is returned.

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

Level	Description	Relevant Code
1	The first call of the power() method passes 5.0 and 4 as arguments. Since the second argument, n, is greater than 1, the power() method is called again in the return statement, with the second argument reduced by 1.	Power(5.0, 4) { if(n > 1) return 5.0*power(5.0, 4-1); ... }
2	The second call of the power() method passes 5.0 and 3 as arguments. Since the second argument, n, is still greater than 1, the power() method is called again in the return statement with the second argument reduced by 1.	Power(5.0, 3) { if(n > 1) return 5.0*power(5.0, 3-1); ... }
3	The third call of the power() method passes 5.0 and 2 as arguments. Since the second argument, n, is still greater than 1, the power() method is called again, with the second argument again reduced by 1.	Power(5.0, 2) { if(n > 1) return 5.0*power(5.0, 2-1); ... }
4	The fourth call of the power() method passes 5.0 and 1 as arguments. Since the second argument, n, is not greater than 1, the value of the first argument, 5.0, is returned to level 3.	Power(5.0, 1) { if(n > 1) ... else return 5.0; }
3	Back at level 3, the value returned, 5.0, is multiplied by the first argument, 5.0, and returned to level 2.	Power(5.0, 2) { if(n>1) ... else return 5.0*5.0; }
2	Back at level 2, the value returned, 25.0, is multiplied by the first argument, 5.0, and returned to level 1.	Power(5.0, 3) { if(n > 1) ... else return 5.0*25.0; }
1	Back at level 1, the value returned, 125.0, is multiplied by the first argument, 5.0, and 625.0 is returned as the result of calling the method in the first instance.	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.