Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Recursion

 
Mr Iftikhar
Ranch Hand
Posts: 39
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can any one give me an example of recursion with
example and please also explain each step of recursion. Or give me a url for simples explaination of recursion. Thanks
 
Johnson Chong
Ranch Hand
Posts: 210
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recursion.....let me see.....suppose you write a program to calculate the factorial of a number. The equation will be like x=y*(y-1)*(y-2)*.....1
So the function would be
fn(x)
If x=1 return 1
else x=x*fn(x-1)
return x*(x-1)
end
I think the fn will works....something like that.
LInk0list and binary tree manipulation uses recursion as well.
Applet manipulation using java recursion......is the fore frontier of cutting edge technology that is fast developing. It is unexplored and it will offer tremendous development potential where's the sky the limit.
-JAC
 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
recursion simply means you are calling a function/procedure/method from within that function/procedure/method
i found one link that explains fairly well
http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm
some people fear using recursion because if you mess up you can cause the computer to hang up
 
Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recursion is as basic mechanism as a loop. Alonzo Church with his lambda calculus proved that any algorithm that can be expressed by "normal" computer language, can be expressed with only function calls, including recursive calls, of course.
But as SICP book wisely noticed, "there is an important difference between mathematical functions and computer procedures. Procedures must be effective." Another restriction: procedures must be understandable by a man of reasonable intelligence Recursion is often inefficient and often hard to understand, that's why is isn't used too often. But certain class of problems is naturally formulated in terms of recursion; for this case a programmer must be accustomed with recursive algorithms.
One such example is XML processing. The language used for it, XSLT, doesn't have loop constructs, only template calls including recursive.
 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i have to agree with map. probly the hardest time i have ever had with figuring out what a program does is if it uses recursion. probly second hardest is too much use of OO. i have given up before when i have to look at 6 different files cause one custom object uses another which uses another...etc.
i say probly cause im not sure which is harder and because i like saying probly
[ April 22, 2002: Message edited by: Randall Twede ]
 
Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Randall Twede:
probly the hardest time i have ever had with figuring out what a program does is if it uses recursion.

Now, if you had spent about 10 years working with recursive functions, you probably wouldn't have such a hard time....
Originally posted by Randall Twede:
probly second hardest is too much use of OO.

Unlike recursion, my feeling about OOP is that it's just too much complicated™ for an average man to be able to grasp. Perhaps the most intelligent of us can do miracles with OOP - great. But according to simple statistics laws, there is never enough wise men. Unfortunately, we have to live with men of average intelligence. That means that our programming constructs should be "idiot frendly" ("Idiots" category includes myself, as the first representative)
 
Rob Ross
Bartender
Posts: 2205
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's why God invented Visual Basic. No pesky objects to worry about.
 
Sameer Jamal
Ranch Hand
Posts: 1870
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Besides programming another example of recursion is when you open a web page and it contains a term that u dont understand and the term is hyperlink, when you click the hyperlink another page that defines the term is displayed. This definition contain another term that you dont understand. The new term is also a hyperlink, so you click it and a page containing its definition is displayed, Once you Understand this definition you click the back button to go back to the previous page where u re-read the term knowing its definition.
(Source Mastering VB 6.0)
 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
sameer,
that seems more like the too many object thing i was talking about. although if you are opening a new window with each link, it seems more like recursion.
[ April 23, 2002: Message edited by: Randall Twede ]
 
Jamie Robertson
Ranch Hand
Posts: 1879
MySQL Database Suse
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Sameer Jamal:
Besides programming another example of recursion is when you open a web page and it contains a term that u dont understand and the term is hyperlink, when you click the hyperlink another page that defines the term is displayed. This definition contain another term that you dont understand. The new term is also a hyperlink, so you click it and a page containing its definition is displayed, Once you Understand this definition you click the back button to go back to the previous page where u re-read the term knowing its definition.
(Source Mastering VB 6.0)
unlike recursion(which always returns a value up the calling method list), your example may throw a "VeryAnnoyedException" if recursion is needed too many times, which would invoke the static method User.swearExcessively( ) and User.addWebsiteToNeverVisitAgainList( url ).
 
Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If to look around carefully, examples of recursion - defining something in terms of itself - are abundant and everywhere.
Today I was reading about a book that teaches layout design, and the author noticed: "Remarkable also is the extent to which the form and layout of design books themselves serve as examples to illustrate important design principles, even though these principles may remain unseated. A wise student will also pay attention to the layout of headings, text, and graphic forms used in the book itself as advocating certain design principles."
Another example, Hacker Writing Style:
Others have been known to criticize glitches in Jargon File drafts by observing (in the mode of Douglas Hofstadter) "This sentence no verb", or "Too repetetetive", or "Bad speling", or "Incorrectspa cing."
 
R K Singh
Ranch Hand
Posts: 5384
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Example of recursion
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If to look around carefully, examples of recursion - defining something in terms of itself - are abundant and everywhere.
Indeed. This thread is another example.
 
Sameer Jamal
Ranch Hand
Posts: 1870
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Randall Twede:
sameer,
that seems more like the too many object thing i was talking about. although if you are opening a new window with each link, it seems more like recursion.
[ April 23, 2002: Message edited by: Randall Twede ]

In recursion when the the function call ends then you move backwards to the complete the previous function calls, so opening new window with each link cannot take you to the previous window so this cannot be the example of recursion
 
Randall Twede
Ranch Hand
Posts: 4467
3
Java Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i guess you are correct and thats why i said seems more like
 
David O'Meara
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Jim Yingst:
[b]Indeed. This thread is another example.

That was what I was going to say, but then I'd be about the 23rd person to admit I was slow
Recursion rocks , I've been guilty of overusing it for years
 
Ravi Veera
Ranch Hand
Posts: 127
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey, how come no one mentioned the classic example of recursion?
Tower of Hanoi
 
Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Randall Twede:
i have to agree with map. probly the hardest time i have ever had with figuring out what a program does is if it uses recursion.

Yes! But then, we do not use recursion a lot in our programs, so I wondered if it were so difficult if we did. There are languages that do not have loop constructions at all, only recursion. Imagine that you spent 10 years programming in such a language, I suspect you would be very comfortable with it.
Indirect confirmation of my theory came from "Structure and Interpretation of Computer Programs" book that I am reading now. It uses Lisp as an illustrative language and all algorithms are based on lists and recursion. First it took me a while to figure how it works; having half of book behind, I got used to it and started to wonder if loops are, in fact, more complex control structure
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
we do not use recursion a lot in our programs
Who's "we"?
 
Michael Ernest
High Plains Drifter
Sheriff
Posts: 7292
Netbeans IDE VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Sameer Jamal:
(A)nother example of recursion is when you open a web page and it contains a term that u dont understand...when you click the hyperlink another page that defines the term is displayed. This definition contain another term that you dont understand. The new term is also a hyperlink, so you click it and a page containing its definition is displayed, Once you Understand this definition you click the back button to go back to the previous page where u re-read the term knowing its definition.

Yiiiiiiiiii....I don't care to think of this as recursion except as one narrow example of using hyperlinks. The explosion of web site development from the early 90's on seemed to me to show that links as a self-describing mechanism was not all that popular, except for the expected forms: FAQs, glossaries, how-to guides.
Link contexts have no rules for observing recursive form, they merely can. So while such a definition covers literal mappings (what's that mean?), it does not address metonymic maps (linked by association, not definition), synecdochal maps (a thing linked to a coherent whole), and of course Isayeva maps (things aimed at linking to the chaotic, subversive recesses of the unwitting reader's subconcious).
But I am still uncomfortable, in that tenured, pompous, emeritus way of expressing discomfort, with the idea that recursion as a technique is somehow limited to the function that calls itself and has a branch condition for terminating the loop. Recursive functions are the densest expression of recursion, and often used as examples because they're brief (and, ironically, hardest to fathom), but they're not the only form available.
 
Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The most general definition of recursion I found is:
"A recursive process is one in which objects are defined in terms of other objects of the same type."
http://mathworld.wolfram.com/Recursion.html
Note that they wisely said "other objects of the same type", not "the same object". Such a broad definition covers these amazing pictures among other things.
Speaking about other things... I am thinking about writing a book review that would consist purely of quotes of Amazon's reviews for this book. If to believe the definition above, it will be an example of a recursive review.
 
Thomas Paul
mister krabs
Ranch Hand
Posts: 13974
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Mapraputa Is:
Speaking about other things... I am thinking about writing a book review that would consist purely of quotes of Amazon's reviews for this book. If to believe the definition above, it will be an example of a recursive review.
That's interesting. I was thinking of writing an entire book that would be made up only of the words and punctuation found in the book "Moby Dick". Or perhaps I'll post a complete post to this forum consisting only of letters of the alphabet! I'll have to think about that one... could be very tough!
 
Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Thomas Paul:
That's interesting. I was thinking of writing an entire book that would be made up only of the words and punctuation found in the book "Moby Dick". Or perhaps I'll post a complete post to this forum consisting only of letters of the alphabet! I'll have to think about that one... could be very tough!

But this would not be a recursion! The definition above said "other objects of the same type". If you write a word that consist of other words... hm, I am sure there are such! As for letters consisting of other letters, German � is "ss" and other languages have letter sequences that would be interpreted as one letter. But all this is only a pale version of such (I am sure) recursively reach letters as Chinese, where one hieroglyph can consist of other
 
Mapraputa Is
Leverager of our synergies
Sheriff
Posts: 10065
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And if we agree that "A recursive process is one in which objects are defined in terms of other objects of the same type", then we all are products of a genuinely recursive process.
 
George Brown
Ranch Hand
Posts: 919
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In response to Map's "A recursive process is one in which objects are defined in terms of other objects of the same type," my favourite example of recursion is the following wabbit (you'll need a C compiler installed to try this):

although I wouldn't recommend compiling and running it on any critical systems. There's not much to explain as far as a walkthrough goes, but suffice to say that the effect would be to put your box into Helen Keller mode.
Since this is my 1000th post I thought I'd post something fun to try...
[ May 10, 2002: Message edited by: George Brown ]
 
Jessica Sant
Sheriff
Posts: 4313
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
<hijack> and very meaningful to have your 1000th post in meaningless drivel Congrats </hijack>
 
Rob Ross
Bartender
Posts: 2205
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hmm, a java version of the above program would be:

However, this isn't recursion ;p Each new thread has a different call stack (or process in the C code has a different global context) . Both basically spawn a new thread that spawns a new thread, ad infinitum.
[ May 10, 2002: Message edited by: Rob Ross ]
[ May 14, 2002: Message edited by: Rob Ross ]
 
Michael Matola
whippersnapper
Ranch Hand
Posts: 1820
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Rob Ross:
However, this isn't recursion ;p
Why not? Is there something special about constructors? Or are you objecting because there's no base case that returns and unwinds?
Each call to Fork() does result in another call to Fork(). Isn't the definition of recursion something along the lines of a function calling itself (either directly or indirectly)?
 
Michael Ernest
High Plains Drifter
Sheriff
Posts: 7292
Netbeans IDE VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
An example of recursion with no unwinding and no return.
[ May 10, 2002: Message edited by: Michael Ernest ]
 
Rob Ross
Bartender
Posts: 2205
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Perhaps you can make the case that this example is a degenerative form of recursion. If that link would open the page in the same window, then I'd be more inclined to call it recursion.
What you have demonstrated though is really a singleton factory pattern!
 
Michael Ernest
High Plains Drifter
Sheriff
Posts: 7292
Netbeans IDE VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A singleton? Where's the protection against either multiple instances of the same type or multiple links (i.e., 'constructors') to spawn the page?
 
Rob Ross
Bartender
Posts: 2205
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There's only one version of this page. It's unique reference is:
http://www.coderanch.com/t/37012/md/Recursion
Everyone using this page is sharing the same reference. It's the same object, from the user's point of view.
 
George Brown
Ranch Hand
Posts: 919
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Rob Ross:
Hmm, a java version of the above program would be: <stuff removed>
I expect it'll run as expected if you make the main method static as well...
[ May 13, 2002: Message edited by: George Brown ]
 
Rob Ross
Bartender
Posts: 2205
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oops. that was a typo. I fixed it now. Thanks.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic