aspose file tools*
The moose likes Java in General and the fly likes Explain to me what is recursion and examples of using it Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Explain to me what is recursion and examples of using it" Watch "Explain to me what is recursion and examples of using it" New topic
Author

Explain to me what is recursion and examples of using it

sailsjam
Greenhorn

Joined: Jul 05, 2001
Posts: 18
I am a beginner to Java and I would like to know what is recursion and example codes of using it.
Cindy Glass
"The Hood"
Sheriff

Joined: Sep 29, 2000
Posts: 8521
There are alot of good conversations on this topic in beginner, intermediate and advanced (and maybe elsewhere). Start with doing a search for "recursion" and reading those.


"JavaRanch, where the deer and the Certified play" - David O'Meara
Arsin Delve
Greenhorn

Joined: Jul 08, 2001
Posts: 29
Recursion, by definition, is an algorithm where a method calls itself to reach a solution.
eg: int aMethod (int a) {
// some code
aMethod (anint);
}
Some real-world problems lend themselves naturally to a recursive solution. There is always some base case, and then you call the method over and over until you reach it and then get the solution that way.
Perhaps the easiest example is using recursion to calculate an exponential (It's not natural but it's simple).
This will calculate x to the power of y
int exponent(int x, int y)
{
if(y==0)
return 1; // anything to the power of 0 is 1
else
return (x * exponent (x, y-1));
}
I hope I got that right!

Paul Michael
Ranch Hand

Joined: Jul 02, 2001
Posts: 697
hey there John! you might want to try listing the contents of directories... and then list also the contents of its subdirectories... i think that would be a good recursion exercise for you.


SCJP 1.2 (89%), SCWCD 1.3 (94%), IBM 486 (90%), SCJA Beta (96%), SCEA (91% / 77%), SCEA 5 P1 (77%), SCBCD 5 (85%)
karl koch
Ranch Hand

Joined: May 25, 2001
Posts: 388
hi,
recursion is good to split problems down to smaller problems.
eg. the listing of directories mentioned above. you split down the problem until it is small enough to handle.
there are several examples on the net that exaplin recursion with "the towers of hanoi" (search for it on google.com or thelike)

karl
jason adam
Chicken Farmer ()
Ranch Hand

Joined: May 08, 2001
Posts: 1932
I'm still learning about recursion myself, but have a quick question/comment about it.
In the above example about the exponential, wouldn't it be better just to use a for loop instead of dealing with the possibility of causing a bunch of errors using recursion? Also, does recursion use more overhead with all the method calls than a loop would? I'm thinking it would, so recursion would be used only when you could rule out a loop, right?
int x = (number to be... exponentialized?)
int y = (exponent)
for( int i = y ; i > 1 ; i-- )
{
x *= x ;
}
Thanks!

[This message has been edited by jason adam (edited July 10, 2001).]
Arsin Delve
Greenhorn

Joined: Jul 08, 2001
Posts: 29
Jason:
Of course you're right! In reality, I would never have used recursion as I did above for all the reasons you've stated - overhead, complexity, etc. I chose it as an example of recursion because it's extremely simple, not because it's a problem well suited to a recursive solution.
I can only think of two real world situations where I've used recursion because I felt it made sense to do so. Once was a directory listing as someone else has already mentioned.
The other (this was C++ mind you, not Java, but it matters not) was a program that given a 2-D maze and a stating point would give insructions on how to navigate to any other point. How I solved the problem was to make a method that moved out in space in each cardinal direction and then called itself recursively until it hit a wall. Eventually, one of the method calls would find the point and then return the directions to get there. All the other method calls would die on the vine.
It worked for mazes that were as big as 100,000 by 100,000 squares, and I always thought that it was amazing since it was a feat that no human could do by hand in any reasonable time frame.
----------------------------------
Arsin Delve, SCJP
sailsjam
Greenhorn

Joined: Jul 05, 2001
Posts: 18
Thanks to everyone I like the response.
AGivant
Greenhorn

Joined: Jun 28, 2001
Posts: 5
Hi!
I like this definition of recursion:
"To define recursion you should define recursion." :-)
Have a nice day.
karl koch
Ranch Hand

Joined: May 25, 2001
Posts: 388
hi,
yes, recursion produces more overhead. you can easely prduce some stackoverflow/out of memory exceptions (i dont remember what exception occured but i made it :-) ) having do deep recursion.
i think the example with the maze is very good. it shows the power of recursion. just split down the problem until you can solve it (move forward one step until you hit a wall).

karl
Pete Cassetta
Greenhorn

Joined: Feb 13, 2001
Posts: 23
Already a lot of helpful replies, but I'll add two cents worth.
In practice, I only use recursion occasionally. But it is a wonderful programming facility, and there are two types of problems which I find easy to solve with recursion but very messy otherwise. The first is traversing a tree structure. Listing all the directories on a computer is a great example. The function just lists the current directory, calling itself for each subdirectory it finds. You can clean up the output by doing the subdirectory calls first (or last) if you like.
The other problem which I find is solved nicely by recursion is parsing/evaluating a formula which involves parentheses. Each time a parenthetical subformula is encountered, the method just calls itself on that subformula, using the result as a term in the main formula. I've also seen this problem solved by converting the expression to a tree then traversing it, by converting it to Reverse Polish Notation (which is easily evaluated using a stack), or with a very inelegant non-recursive solution.
By the way, recursion has been around a long time. People have been writing recursive functions in Assembly, Pascal, C, etc. long before Java was born. So it's not anything specific to Java.
Jim Rock
Ranch Hand

Joined: Mar 20, 2001
Posts: 39
If you really want to understand recursion and recursive algorithms a good book on the subject might to helpful.
Simon Xu
Ranch Hand

Joined: Aug 16, 2000
Posts: 235
hi,
I have a problem when tracing the recursion in Merge sort. We have two recursion calls, but how to trace them? Does the second call begins after the first call finishes?
Thanks
Craig Rodway
Greenhorn

Joined: Jan 07, 2003
Posts: 1
Recursion is self-explanatory.
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
Every recursive function can be rewritten using iteration (you can just create a method call stack manually if necessary). The trick is determining which solution is best for a particular problem, if both solutions are clear enough.
Take the exponent() function. There's a faster version that takes advantage of this property: a^(2b) = (a^b)*(a^b)

Try writing that in iterative form. It's possible, but the result won't be as clear and simple to understand as the recursive version. Some problems are better solved with recursion, and some with iteration--it really depends on the problem.
[ January 07, 2003: Message edited by: David Weitzman ]
Hmmmm. Did UBB discard part of my message? Strange. I'm adding it back.
[ January 07, 2003: Message edited by: David Weitzman ]
Cindy Glass
"The Hood"
Sheriff

Joined: Sep 29, 2000
Posts: 8521
Originally posted by Craig Rodway:
Recursion is self-explanatory.

 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Explain to me what is recursion and examples of using it