Explain to me what is recursion and examples of using it

[sailsjam]

I am a beginner to Java and I would like to know what is recursion and example codes of using it.

[Cindy Glass]

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.

[Arsin Delve]

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]

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.

[karl koch]

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]

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]

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]

Thanks to everyone I like the response.

[AGivant]

Hi!
I like this definition of recursion:
"To define recursion you should define recursion." :-)
Have a nice day.

[karl koch]

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]

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]

If you really want to understand recursion and recursive algorithms a good book on the subject might to helpful.

[Simon Xu]

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]

Recursion is self-explanatory.

[David Weitzman]

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)

int exponent(int base, int power) {
  if (power == 0) return 1;
 
  if (power % 2 == 0) /* power is even */
  {
    int aToHalfPower = exponent(base, power/2);
    return aToHalfPower * aToHalfPower;
  }
  else /* power is odd */
  {
    return base * exponent(base, power - 1);
  }
}

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]

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