Recursion in java

By: aathishankaran Emailed: 1674 times Printed: 2150 times    

Latest comments
By: rohit kumar - how this program is work
By: Kirti - Hi..thx for the hadoop in
By: Spijker - I have altered the code a
By: ali mohammed - why we use the java in ne
By: ali mohammed - why we use the java in ne
By: mizhelle - when I exported the data
By: raul - no output as well, i'm ge
By: Rajesh - thanx very much...
By: Suindu De - Suppose we are executing

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.


Java Home | All Java Tutorials | Latest Java Tutorials

Sponsored Links

If this tutorial doesn't answer your question, or you have a specific question, just ask an expert here. Post your question to get a direct answer.



Bookmark and Share

Comments(52)


1. View Comment

Thx for the explanation, I understand what recursion means in java now.

View Tutorial          By: Tina at 2008-12-15 16:39:27
2. View Comment

Comment: yes i understood too:D:D perfect and breif explanation..thnx alot
eman from (german univercity in cairo)


View Tutorial          By: eman at 2009-04-21 23:57:26
3. View Comment

this is really cool......

View Tutorial          By: solex at 2009-05-16 04:02:35
4. View Comment

example is ok, but plz increases the standard of example a little bit high with real time. It's equal to class room

View Tutorial          By: venky at 2009-05-19 01:29:04
5. View Comment

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"

View Tutorial          By: Cheeseman at 2009-05-19 10:12:11
6. View Comment

Explanation was good and easily comprehendable.

View Tutorial          By: Moin Adil at 2009-06-17 04:18:56
7. View Comment

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


View Tutorial          By: Ankit Shukla at 2009-09-17 15:25:17
8. View Comment

...indeed its a helpful brief explanation, coz our instructor want us to explore more deeper the recursion in java, tnx

View Tutorial          By: elaine22 at 2010-01-22 01:27:16
9. View Comment

Plz can u give me some more examples of recursion...
thnx alot for the explanation
its really very help full


View Tutorial          By: Asadullah at 2010-01-23 06:38:58
10. View Comment

i find out this example quite heplful thnx adimn......:)

View Tutorial          By: ayaz pathan ( MUET) at 2010-02-21 10:40:18
11. View Comment

nice...cleared this example....

View Tutorial          By: Waqas Mughal at 2010-03-13 21:21:46
12. View Comment

this is genius.
you are a master of recursion


View Tutorial          By: Chandler at 2010-03-26 09:56:08
13. View Comment

Good Information... Plz give some more examples with explaination

View Tutorial          By: Uetian at 2010-04-01 04:26:55
14. View Comment

can we do it this procedure by iteration i know that is simple way but it's complicated thanks

View Tutorial          By: sattar at 2010-05-03 03:00:20
15. View Comment

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.


View Tutorial          By: Uriah at 2010-05-08 18:59:16
16. View Comment

thank u.actually i want little more...

View Tutorial          By: burhan at 2010-07-13 03:46:01
17. View Comment

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?


View Tutorial          By: Gaurav at 2010-08-08 01:08:27
18. View Comment

it's real nice explanation

View Tutorial          By: Shreya at 2010-09-10 11:24:11
19. View Comment

thanks alot!

View Tutorial          By: gumuruh at 2010-11-06 11:27:18
20. View Comment

thanks for suppporting us

View Tutorial          By: sonia at 2010-11-29 00:46:56
21. View Comment

some more examples should be given...

View Tutorial          By: flora at 2010-12-08 03:32:50
22. View Comment

I think u've done well, just that more examples will have been very appropriate.

View Tutorial          By: Mac at 2011-01-23 10:22:10
23. View Comment

thanks ....

View Tutorial          By: shiva at 2011-02-28 11:16:32
24. View Comment

Thanks for everything... I'm greeting you from Azerbaijan,Baku...

View Tutorial          By: Shahriyar at 2011-04-28 15:54:14
25. View Comment

i like this a lot

View Tutorial          By: raj at 2011-05-06 06:15:36
26. View Comment

Plz show me how to use main method reccurssively plz

View Tutorial          By: Jyoti Bankar at 2011-07-14 10:31:53
27. View Comment

result = fact (n-1) * n;
i didn't got this concept ..
if i put n=3 then the answer is
(3-1)*3 = 6
and if i put n=4 the answer is
(4-1) *4= 12 but the real answer is 24 .how it's so. can u plz explain me . how it exactly works.


View Tutorial          By: praveen at 2011-08-07 20:22:09
28. View Comment

recursive programs that ask the user to enter the name of the file or path

View Tutorial          By: siyabonga at 2011-08-10 08:34:44
29. View Comment

give an recursive example using string

View Tutorial          By: sauk at 2011-08-22 16:16:41
30. View Comment

How can you print this using recursion?


tab
b
ab
tab

I got my code correct , but its just that the whole thing repeats twice.


View Tutorial          By: Menon at 2011-09-08 07:16:02
31. View Comment

Now what the hell does all this mean???
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.


View Tutorial          By: Søren at 2011-09-22 03:13:53
32. View Comment

CTRL+C then CTRL+V :P
Complete Reference ;)


View Tutorial          By: Rahul A at 2012-03-21 14:12:56
33. View Comment

Dear author
u missed check condition for 0(Zero)
so u must be write in if(n==0 || n==1) this is perfect condition.

Thanks a lot for providing this kind of codes.


View Tutorial          By: Maroof Ahmad at 2012-03-28 14:59:53
34. View Comment

It takes me time to understand the process of the factorial example. I think the explanation would be better if it has written as steps, not a paragraph. Anyway, it was really helpful.
Thanks


View Tutorial          By: Abdullah Ibrahim at 2012-04-11 00:38:23
35. View Comment

Hagti hain.. the complete program has been copy pasted from JAVA Complete Reference including explanation.. give credit where its due.. not that explanation made me understand the concept but still.. anyway.. folks who didnt quite understand the solution.. here's the explanation.. Link : http://stackoverflow.com/questions/8183426/factorial-using-recursion-in-java

View Tutorial          By: Macho Man at 2012-06-21 07:58:03
36. View Comment

thanks...please give some more examples

View Tutorial          By: Iqra at 2012-06-24 18:57:51
37. View Comment

Thanks for the article. I finally finish my task about it.. and thanks for clear explanation.. :D

View Tutorial          By: bali web at 2012-07-10 13:47:49
38. View Comment

@Iqra :

You're welcome. Use sites like stack overflow and check out Complete Reference as these guys have almost lifted every word off the book.


View Tutorial          By: Macho Man at 2012-07-16 08:02:14
39. View Comment

the example program that given above for recursion program is not executed currectly, thanks for that

View Tutorial          By: bharathi at 2012-07-17 09:31:14
40. View Comment

can anyone explain the output of this recursive example???
class a
{
static int c=1;
public static void main(String ar[])
{

recur(4);

}

public static void recur(int n)
{

for(int i=0;i<n;i++)
{

recur(n-1);
System.out.println(c);
c++;

}


}


}


View Tutorial          By: vipul at 2012-08-12 19:41:19
41. View Comment

Thanks for the explanation. I had read about this topic earlier but I wasn't able comprehend it. Now I have understood the concept clearly.

View Tutorial          By: Sidharth Sahoo at 2012-09-12 16:26:07
42. View Comment

Declaring int result within the method will change the value of result each time you run the method, there is an alternative method :

class Factorial {

int fact(int n)
{
if ( n ==1) return 1;
return n* fact (n-1);
}
}

therefore taking the additional variable 'result' was completely unnecessary. Im in the twelfth grade.


View Tutorial          By: Soph at 2013-02-06 06:11:39
43. View Comment

class Factorial
{
int fact(int n)
{
if ( n ==1) return 1;
return n* fact (n-1) ;
}

}


View Tutorial          By: soph at 2013-02-06 06:49:07
44. View Comment

thank you for code

View Tutorial          By: turki at 2013-12-11 13:23:44
45. View Comment

I don't undrstnd.. cz I think in recurs the method again n again calls itself.. but in this pgm there is not such a case shown...

View Tutorial          By: Alina Ali at 2014-11-13 03:06:17
46. View Comment

thanks!

View Tutorial          By: leny at 2014-12-09 04:00:44
47. View Comment

thanks , but i want it some thing like fibonici series
wher it returns(fib(----)+fib(----)
i want to understand this when it returns 2 values at the same time


View Tutorial          By: Arpit Agrawal at 2015-01-04 18:34:41
48. View Comment

it really helped me...thank you...

View Tutorial          By: ram at 2015-01-22 20:12:01
49. View Comment

realy i enjoy it for visit your site. and i understand this resursion function.

View Tutorial          By: vinod balot at 2015-02-09 17:43:30
50. View Comment

great explanations.. some important words are missing for example... calling itself REPEATED... there is no repeat word... so that it may recursive

View Tutorial          By: Joshua Paul at 2015-04-14 03:43:44
51. View Comment

nice explanation indeed, but can u please explain me the type of recursion?

View Tutorial          By: ishika at 2015-06-23 09:16:16
52. View Comment

Thank you!!

View Tutorial          By: Diego at 2015-07-16 21:11:58

Your name (required):


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


Your sites URL (optional):


Your comments:



More Tutorials by aathishankaran
Web Security Issues
The Web User's Perspective
Server-side plug-Ins
The best way to avoid security vulnerabilities with new server
JavaScript Security
Window Object
Working with Status Bar Messages
Retrieving a Portion of a String
Referencing Windows
Math Object
Frame Object
Document Object
Closing Windows
Built-in Object in Javascript
Textarea Object

More Tutorials in Java
Update contents of a file within a jar file
Tomcat and httpd configured in port 8080 and 80
Java File
Java String
Count number of vowels, consonants and digits in a String in Java
Reverse a number in Java
Student marks calculation program in Java
Handling Fractions in Java
Calculate gross salary in Java
Calculate average sale of the week in Java
Vector in Java - Sample Program
MultiLevel Inheritance sample in Java
Multiple Inheritance sample in Java
Java program using Method Overriding
Java program to check if user input is an even number

More Latest News
Most Viewed Articles (in Java )
Recursion in java
The Basic Structure of a Simple Java program
FileReader and FileWriter example program in Java
Read from a COM port using Java program
How to use Iterator in Java
XML and Java - Parsing XML using Java Tutorial
How to Send SMS using Java Program (full code sample included)
Count number of vowels, consonants and digits in a String in Java
Student marks calculation program in Java
Java program to calculate volume of a Box
Text to Speech conversion program in Java
Stack example in Java - push(), pop(), empty(), search()
Vector example in Java
setPriority() and getPriority() in Java
The Main Thread in Java
Most Emailed Articles (in Java)
Vector in Java - Sample Program
FilenameFilter - sample program in Java
Update contents of a file within a jar file
Tomcat and httpd configured in port 8080 and 80
What is a deadlock and how to avoid it in Java
How to use ArrayList in Java
Count number of vowels, consonants and digits in a String in Java
Java program using Method Overriding
Get user input in Java
Read a file line by line in Java - Sample Program
Java program for changeable wrapper class
SimpleDateFormat sample program in Java
concat(), replace(), and trim() Strings in Java
how to use boolean data type in Java
Using StringTokenizer in Java