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 (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 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(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 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 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.

2007-03-08

Comments(17)

1.	Thx for the explanation, I understand what recursion means in java now. By: Tina at 2008-12-15 16:39:27
2.	Comment: yes i understood too:D:D perfect and breif explanation..thnx alot eman from (german univercity in cairo) By: eman at 2009-04-21 23:57:26
3.	this is really cool...... By: solex at 2009-05-16 04:02:35
4.	example is ok, but plz increases the standard of example a little bit high with real time. It's equal to class room By: venky at 2009-05-19 01:29:04
5.	Good explanation but I think there's a slight mistake in the output. It give's the "intended" results but the text before all three outputs says "Factorial of 3" for all instead of "Factorial of 4 or 5" By: Cheeseman at 2009-05-19 10:12:11
6.	Explanation was good and easily comprehendable. By: Moin Adil at 2009-06-17 04:18:56
7.	example is good for understand what is the function of recursion but i think in additional there is one more example of recursion.along with By: Ankit Shukla at 2009-09-17 15:25:17
8.	...indeed its a helpful brief explanation, coz our instructor want us to explore more deeper the recursion in java, tnx By: elaine22 at 2010-01-22 01:27:16
9.	Plz can u give me some more examples of recursion... thnx alot for the explanation its really very help full By: Asadullah at 2010-01-23 06:38:58
10.	i find out this example quite heplful thnx adimn......:) By: ayaz pathan ( MUET) at 2010-02-21 10:40:18
11.	nice...cleared this example.... By: Waqas Mughal at 2010-03-13 21:21:46
12.	this is genius. you are a master of recursion By: Chandler at 2010-03-26 09:56:08
13.	Good Information... Plz give some more examples with explaination By: Uetian at 2010-04-01 04:26:55
14.	can we do it this procedure by iteration i know that is simple way but it's complicated thanks By: sattar at 2010-05-03 03:00:20
15.	Like every other Java recursion example, this example uses either (a) factorial or fibonacci, or (b) a recursive method that returns a void. Not high-quality examples for teaching others who do not yet understand. Better is a recursive method that inputs and returns a string. Try again to make a better example. By: Uriah at 2010-05-08 18:59:16
16.	thank u.actually i want little more... By: burhan at 2010-07-13 03:46:01
17.	The code to show recursion is ok, but the declaration of variables should be done outside the function to save some cycles of cpu. can it be posted? By: Gaurav at 2010-08-08 01:08:27

Your name (required):


Your email(required, will not be shown to the public):


Your sites URL (optional):


Your comments:

Enter Code: