Win a copy of Kotlin Cookbook this week in the Kotlin forum!
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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Liutauras Vilda
• Bear Bibeault
• Paul Clapham
• Jeanne Boyarsky
Sheriffs:
• Junilu Lacar
• Knute Snortum
• Henry Wong
Saloon Keepers:
• Ron McLeod
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• Carey Brown
Bartenders:
• Frits Walraven
• Joe Ess
• salvin francis

# Recursion

Ranch Hand
Posts: 39
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

Ranch Hand
Posts: 210
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

Ranch Hand
Posts: 4702
9
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

Leverager of our synergies
Posts: 10065
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: 4702
9
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
Posts: 10065

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)

Bartender
Posts: 2205
That's why God invented Visual Basic. No pesky objects to worry about.

Ranch Hand
Posts: 1871
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: 4702
9
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 ]

Ranch Hand
Posts: 1879

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
Posts: 10065
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."

Ranch Hand
Posts: 5390
1
Example of recursion

Wanderer
Posts: 18671
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: 1871

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: 4702
9
i guess you are correct and thats why i said seems more like

Rancher
Posts: 13459

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

Ranch Hand
Posts: 127
Hey, how come no one mentioned the classic example of recursion?
Tower of Hanoi

Mapraputa Is
Leverager of our synergies
Posts: 10065

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
Posts: 18671
we do not use recursion a lot in our programs
Who's "we"?

High Plains Drifter
Posts: 7292

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
Posts: 10065
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.

mister krabs
Posts: 13974

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
Posts: 10065

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
Posts: 10065
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.

Ranch Hand
Posts: 919
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 ]

Sheriff
Posts: 4313
<hijack> and very meaningful to have your 1000th post in meaningless drivel Congrats </hijack>

Rob Ross
Bartender
Posts: 2205
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 ]

whippersnapper
Posts: 1843
5
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
Posts: 7292
An example of recursion with no unwinding and no return.
[ May 10, 2002: Message edited by: Michael Ernest ]

Rob Ross
Bartender
Posts: 2205
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
Posts: 7292
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
https://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

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
Oops. that was a typo. I fixed it now. Thanks.

 I am Arthur, King of the Britons. And this is a tiny ad: Sauce Labs - World's Largest Continuous Testing Cloud for Websites and Mobile Apps https://coderanch.com/t/722574/Sauce-Labs-World-Largest-Continuous