Explain Recursion In Java With Program And Explanation
In This Topic & Blog Having Any Query Then Post your Comment and Suggestion Below
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
, 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
. T
o 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 function 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] 0
[1] 1
[2] 2
[3] 3
[4] 4
[5] 5
[6] 6
[7] 7
[8] 8
[9] 9