Java supports recursion. Recursion
is the process of defining something in terms of itself. As it relates to java
programming, recursion is the attribute that allows a method to call itself. A
method that calls itself is said to be recursive.
The classic example of recursion is the computation of the factorial of a
number. The factorial of a number N is the product of all the whole numbers
between 1 and N. for example, 3 factorial is 1×2×3, or 6. Here is how a
factorial can be computed by use of a recursive method.
class
Factorial {
int fact(int n) {
int result;
if ( n ==1) return 1;
result = fact (n1) * n;
return result;
}
}
class
Recursion {
public static void main (String args[]) {
Factorial f =new Factorial();
System.out.println(“Factorial of 3 is “ + f.fact(3));
System.out.println(“Factorial of 3 is “ + f.fact(4));
System.out.println(“Factorial of 3 is “ + f.fact(5));
}
}
The output from this program is shown here:
Factorial of 3 is 6
Factorial of 4 is 24
Factorial of 5 is 120
If you are unfamiliar with
recursive methods, then the operation of fact()
may seem a bit confusing. Here is how it works. When fact() is called with
an argument of 1, the function returns 1; otherwise it returns the product of fact(n1)*n.
to evaluate this expression, fact() is
called with n1. this process repeats
until n equals 1 and the calls to the
method begin returning.
To better understand how the fact() method
works, let’s go through a short example. When you compute the factorial of 3,
the first call to fact() will cause a
second call to be made with an argument of 2. this invocation will cause fact() to be called a third time with an argument of 2. This call
will return 1, which is then be called a third time with an argument of 1. This
call will return1, which is then multiplied by 2 (the value of n
in the second invocation). This result (which is 2) is then returned to the
original invocation of fact() and
multiply by 3 ( the original value of n).
This yields the answer, 6. You might find it interesting to insert println()
statements into fact() which will
show at what level each call is and what the intermediate answers are.
When a method calls itself, new local variables and parameters are allocated
storage on the stack, and the method code is executed with these new variables
from the start. A recursive call does not make a new copy of the method. Only
the arguments are new. As each recursive call returns, the old local variables
and parameters are removed from the stack, and execution resumes at the point of
the call inside the method. Recursive methods could be said to “telescope”
out and back.
Recursive versions of many routines may execute a bit more slowly than the
iterative equivalent because of the added overhead of the additional function
calls. Many recursive calls to a method could cause a stack overrun. Because
storage for parameters and local variables, it is possible that the stack could
be exhausted. If this occurs, the java runtime system will cause an exception.
However, you probably will not have to worry about this unless a recursive
routine runs wild.
The main advantage to recursive methods is that they can be used to
create clearer and simpler versions of several algorithms than can their
iterative relatives. For example, the QuickSort sorting algorithm is quite
difficult to implement in an iterative way.
