Recursion
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:
// A simple example of recursion.
class Factorial {
// this is a recursive method
int fact(int n) {
int result;
if(n==1) return 1; result =
fact(n-1) * 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 4 is "
+ f.fact(4)); System.out.println("Factorial of 5 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(n–1)*n. To evaluate
this expression, fact( ) is called
with n–1. 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 1. This call will return 1, 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 multiplied
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. 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 method calls. Many recursive calls to a
method could cause a stack overrun. Because storage for parameters and local
variables is on the stack and each new call creates a new copy of these
variables, it is possible that the stack could be exhausted. If this occurs,
the Java run-time 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. Also, some types of AI-related algorithms are most easily
implemented using recursive solutions.
When writing recursive
methods, you must have an if
statement somewhere to force the method to return without the recursive call
being executed. If you don’t do this, once you call the method, it will never
return. This is a very common error in working with recursion. Use println( ) statements liberally during
development so that you can watch what is going on and abort execution if you
see that you have made a mistake.
Here is
one more example of recursion. The recursive method printArray( ) prints the first i
elements in the array values.
// Another example that uses recursion.
class RecTest { int values[];
RecTest(int i) { values = new
int[i];
}
// display array -- recursively
void printArray(int i) {
if(i==0) return; else
printArray(i-1);
System.out.println("[" + (i-1) +
"] " + values[i-1]);
}
}
class Recursion2 {
public static void
main(String args[]) { RecTest ob = new RecTest(10);
int i;
for(i=0; i<10; i++) ob.values[i] = i;
ob.printArray(10);
}
}
This program generates the
following output:
0
1
2
3
4
5
6
7
8
9
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.