• Post Reply Bookmark Topic Watch Topic
  • New Topic

What is recursion?  RSS feed

 
Mujahid olabomi Raji
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can someone give a simple definition,explanation and example(s) on the use of recursion in java?
 
William P O'Sullivan
Ranch Hand
Posts: 859
Chrome IBM DB2 Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
definition of recursion: See recursion!


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


WP
 
Bear Bibeault
Author and ninkuma
Marshal
Posts: 66307
152
IntelliJ IDE Java jQuery Mac Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"What is X?" questions are best answered with a google search. Then you can post specific questions that you might have.
 
D. Wang
Greenhorn
Posts: 3
Eclipse IDE Java Windows Vista
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:

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
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 56599
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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)^ ; ¬gskip
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
Ranch Hand
Posts: 4696
8
Java Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 56599
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!