• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Explain to me what is recursion and examples of using it

 
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am a beginner to Java and I would like to know what is recursion and example codes of using it.
 
"The Hood"
Posts: 8521
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!

 
Ranch Hand
Posts: 697
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 388
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Chicken Farmer ()
Posts: 1932
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 29
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks to everyone I like the response.
 
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi!
I like this definition of recursion:
"To define recursion you should define recursion." :-)
Have a nice day.
 
karl koch
Ranch Hand
Posts: 388
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 39
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you really want to understand recursion and recursive algorithms a good book on the subject might to helpful.
 
Ranch Hand
Posts: 235
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Recursion is self-explanatory.
 
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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"
Posts: 8521
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Craig Rodway:
Recursion is self-explanatory.


 
We're all out of roofs. But we still have tiny ads:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic