Re: Java Questions Again: What's So Great About Recursion

  • From: Dave <davidct1209@xxxxxxxxx>
  • To: programmingblind@xxxxxxxxxxxxx
  • Date: Thu, 7 Apr 2011 14:40:03 -0700

Echoing pretty much what everyone else has to say...recursion reflects
some deep mathematical properties so that you can prove the
correctness of a recursive algorithm using induction trivially (among
other things).

It's also handy to traverse a tree structure; often, you will
visualize the calls made by a recursive functions in the form of a
tree for this reason.  Take a merge sort algorithm below:

mergesort(array A[a_1, ..., a_n]):
merge(mergesort(a_1, ..., a_(n/2)), mergesort(a_(n/2+1), ..., a_n))

where merge combines two sorted arrays into a single sorted array.

Sina's right about call stack memory being constrained by the OS; the
stack has a specific limit of memory allocated per process.

On 4/7/11, Sina Bahram <sbahram@xxxxxxxxx> wrote:
> Let's not confuse memory with stack space please.
>
> Every time you have a recursive function call, you need another stack frame
> or function record popped on, and that stack has a
> limited capacity. Whether it's 256 bytes for a small model, 4K for a medium,
> or large at 65K, it's still not that huge . now, I
> think the stack model has been revamped in later versions of the kernel in
> Windows/Linux, but the point is it has nothing to do with
> the fact that you have 4GB of ram versus 256MB of ram back in the day.
>
> So yes, memory is cheap, but recursion depth still is very much
> excruciatingly small.
>
> Take care,
> Sina
>
> From: programmingblind-bounce@xxxxxxxxxxxxx
> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Ken Perry
> Sent: Thursday, April 07, 2011 2:12 PM
> To: programmingblind@xxxxxxxxxxxxx
> Subject: RE: Java Questions Again: What's So Great About Recursion
>
>
>
> Tylor is correct that recursion is great on algorithms that deal with trees
> whether it is for sorting or searching or even writing
> or reading them from or to disk.
>
> A couple more reasons for them.
>
> 1)      They can make rather large loops look really small and easy to
> upkeep at the cost of memory.  Note how cheap memory is now
> days.
> 2)      Some things are just easier to do with recursion for example the
> knights tour problem is not so easy to do with loops
> 3)      Some weird languages don't have great looping structures and
> recursion can help you there.
>
> Now if you're in for a good joke just search for "recursion" on google.  You
> will notice that the google programmers can be funny.
> Google will ask you.  Did you mean recursion?  Then you click on that and
> guess what it asks if you mean "recursion"?  again. You
> can click that all day long if you like.
>
> Ken
>
> From: programmingblind-bounce@xxxxxxxxxxxxx
> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Stanzel, Susan -
> Kansas
> City, MO
> Sent: Thursday, April 07, 2011 1:45 PM
> To: programmingblind@xxxxxxxxxxxxx
> Subject: RE: Java Questions Again: What's So Great About Recursion
>
> Hi Listers,
>
> I have asked the Java teacher to enlighten me on this subject of recursion.
> I have wondered what it was for also, but it was just
> one of those things I didn't bother to ask.
>
> Susie
>
> From: programmingblind-bounce@xxxxxxxxxxxxx
> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Stanzel, Susan -
> Kansas
> City, MO
> Sent: Thursday, April 07, 2011 12:32 PM
> To: programmingblind@xxxxxxxxxxxxx
> Subject: RE: Java Questions Again: What's So Great About Recursion
>
> Hi Listers,
>
> Java has a serialization mechanism to do that kind of tracking.
>
> Susie
>
> From: programmingblind-bounce@xxxxxxxxxxxxx
> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Homme, James
> Sent: Thursday, April 07, 2011 12:16 PM
> To: programmingblind@xxxxxxxxxxxxx
> Subject: RE: Java Questions Again: What's So Great About Recursion
>
> Hi Ty,
> Is it done when it has finished reading the file?
>
> Thanks.
>
> Jim
>
> Jim Homme,
> Usability Services,
> Phone: 412-544-1810. Skype: jim.homme
> Highmark recipients,  Read my accessibility blog
> <http://mysites.highmark.com/personal/lidikki/Blog/default.aspx> . Discuss
> accessibility here
> <http://collaborate.highmark.com/COP/technical/accessibility/default.aspx> .
> Accessibility Wiki: Breaking news
> and accessibility advice
> <http://collaborate.highmark.com/COP/technical/accessibility/Accessibility%20Wiki/Forms/AllPages.aspx>
>
> From: programmingblind-bounce@xxxxxxxxxxxxx
> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Littlefield,
> Tyler
> Sent: Thursday, April 07, 2011 12:59 PM
> To: programmingblind@xxxxxxxxxxxxx
> Subject: Re: Java Questions Again: What's So Great About Recursion
>
> Jim:
> Recursion has a limited number of applications where it is actually more
> useful than a loop, I'll give one I use it for.
> In my game engine, properties are stored in a tree setup with a root
> property and all other properties work from there. so, you
> could essentially have stats.health, stats.mana, etc. stats is the root
> node, health are the children nodes on stats.
> Now, here's where recursion comes in handy.
> when I serialize this tree, I write it all in xml. so I'll serialize the
> stats, then I'll serialize health. what I do is something
> like this:
> Serialize(XMLNode, property)
> so lets say that stats.health has two properties: stats.health.hp, and
> stats.health.max_hp. in order to serialize that I would have
> to loop through the properties of stats.health, then if hp were to have
> another property I'd have to loop through those, which could
> get messy.
> Rather than do that though, I use recursion. so the serialization setup
> calls serialize on stats, passing the root, then that
> function calls serialize on stats.health passing health.
> I hope I explained that properly. Essentially in summary, it allows me to
> keep passing in each node of the tree until I am finally
> done. I can recurse until I get done serializing a branch, at which point I
> will pop back to where i was because the recursion will
> return when it's done.
>
> On 4/7/2011 10:51 AM, Homme, James wrote:
> Hi,
> It's probably my ignorance coming out to bite me again, but I just was
> reading about recursion in my Java book and thinking that it
> isn't all that useful because you can do the same stuff with a loop. Maybe
> the book examples are so simple that I just don't see
> it's usefulness. They were even saying that recursion eats up more memory
> than loops do, so I'm wondering why I learned it in the
> first place, other than to know how it works and that it exists.
>
> Please help.
>
> Thanks.
>
> Jim
>
> Jim Homme,
> Usability Services,
> Phone: 412-544-1810. Skype: jim.homme
> Highmark recipients,  Read my accessibility blog
> <http://mysites.highmark.com/personal/lidikki/Blog/default.aspx> . Discuss
> accessibility here
> <http://collaborate.highmark.com/COP/technical/accessibility/default.aspx> .
> Accessibility Wiki: Breaking news
> and accessibility advice
> <http://collaborate.highmark.com/COP/technical/accessibility/Accessibility%20Wiki/Forms/AllPages.aspx>
>
>
>
> This e-mail and any attachments to it are confidential and are intended
> solely for use of the individual or entity to whom they are
> addressed. If you have received this e-mail in error, please notify the
> sender immediately and then delete it. If you are not the
> intended recipient, you must not keep, use, disclose, copy or distribute
> this e-mail without the author's prior permission. The
> views expressed in this e-mail message do not necessarily represent the
> views of Highmark Inc., its subsidiaries, or affiliates.
>
> --
>
> Thanks,
> Ty
>
__________
View the list's information and change your settings at 
//www.freelists.org/list/programmingblind

Other related posts:

  1. Home
  2. programmingblind
  3. Archive
  4. 04-2011