What is recursion?

[Mujahid olabomi Raji]

Can someone give a simple definition,explanation and example(s) on the use of recursion in java?

[William P O'Sullivan]

definition of recursion: See recursion!


Seriously, this has been asked more than once before.
Please use the search function.


WP

[Bear Bibeault]

"What is X?" questions are best answered with a google search. Then you can post specific questions that you might have.

[D. Wang]

Recursion is where a function calls itself. It usually starts with a designated "base case" that defines when the method should exit/return. For example:

public class showRecursion{
   public static void main(String[] args){
      keepAdding(0);
   }
   public int keepAdding(int sum){
      if(sum==10) return;
      sum += 1;
      keepAdding(sum);
   }

As you may notice, recursion is almost like a for loop. It actually is sort of like a for loop, except it is usually used when you don't know when the loop should end.

[Jeff Verdegan]

D. Wang wrote:Recursion is where a function calls itself.

It would have been better to let the OP follow the excellent advice he was given to search the web.

As you may notice, recursion is almost like a for loop.

Not really, no.

except it is usually used when you don't know when the loop should end.

No, that's definitely not what separates iteration from recursion. Equivalent knowns and unknowns in the stopping condition can be used in either case.

[Henry Wong]

Jeff Verdegan wrote:

As you may notice, recursion is almost like a for loop.

Not really, no.

Recursion can be used to replace a loop. The most common technique of this is a "tail recursion", where the last execution of the code is a recursive call to handle the next iteration.

In most cases though, recursion is used where a loop just isn't feasible -- for example, to walk a tree.... So, as Jeff stated, "Not really. No".

Henry

[Campbell Ritchie]

Disagree. A loop is like recursion. If you look at generalised substitution language, the definition of recursion and iteration (loops) are identical, something like
while g do S end =df  (g ⟹ S)^ ; ¬g ⟹ skip
which is the transitive closure of a guarded substitution, followed by a skip.
I heard that Turing defined structured programming as programming that used sequence selection and recursion, thirty-something years before Böhm and Jacopini defined it as sequence selection and iteration.

And D Wang’s example does not fit his description, I am afraid. Because that is not a “function” calling itself. It is not a “function” because it doesn’t return anything. If it returned something, then it might be recursion. It won’t actually compile because it doesn’t return an int from every path of execution. It would be recursion if it returned a value to be used by itself, however.

[Randall Twede]

recursion is easy for the computer, but hard for humans.
many times a recursive program is much shorter and faster than alternative methods, but it is just not the way humans think.
just my opinion.

[Winston Gutkowski]

Campbell Ritchie wrote:I heard that Turing defined structured programming as programming that used sequence selection and recursion, thirty-something years before Böhm and Jacopini defined it as sequence selection and iteration.

Ooof. Too much maths for me. Actually, I liked William's reference; although I believe the quote is:

To understand recursion, you must first understand recursion.



Winston

[Campbell Ritchie]

Winston Gutkowski wrote:. . . Actually, I liked William's reference; although I believe the quote is:

To understand recursion, you must first understand recursion. . . .

Agree. They are so much better, but would any of the greenhorns understand them? I use recursion all the time in my compiler (yes, I know you are not supposed to use recursion in compilers), and I long ago gave up trying to understand it. I simply use it, knowing it will work.