
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 xn1 by x. To put this in terms of a specific example, we can calculate 2^{4} as 2^{3} multiplied by 2, and we can get 2^{3} by multiplying 2^{2} by 2, and 2^{2} is produced by multiplying 2^{1}, which is 2 of course, by 2.
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, n1); // 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^{4}.
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.