[clug-progsig] Recursion (was Javascript how to write to a <textarea>)
Shawn
sgrover at open2space.com
Fri Feb 25 01:22:49 PST 2005
On Friday 25 February 2005 00:20, Rob S wrote:
> As far as i've been able to figure out, with the code from the last
> message (forgive me if I repeat part of the message):
> x = 4, y = 3;
> Add(4, 3)
>
> | turns into
>
> --- Add(5, 2)
>
> ---Add(6, 1)
>
> ----Add(7,0)
>
> ---What happens here?
>
> The function is called with (x= 7, y = 0), so the function returns a 0.
> What does this mean? The function returns a '0', which
> somehow unwinds the recursion. Do the previous iterations return 0's
> themselves? Do the values change as the recursive loop gets unwinded?
> Does the code unwind itself at all? or does it simply return a 0 to the
> original call and ends? Or does each iteration return a 0 to the one
> that spawned it? Or does it return the finishing value?
picture in your head the program flow (or order of processing). Each time the
Add() function gets called a placeholder is remembered - this is where we
come back to when the current instance of the function call is completed.
So, if you follow the program flow (your tree above is a good example to go
from), then we hit the condition where y=0, and this ends the recursion. At
this point, zero is returned to the calling statement (the "Add(7,0)"
evaluates to "0"). Now that calling statement has a value to work with, and
completes it's processing and does it's own return.
That said, I can see why this is a confusing example - the function returns
"Add(x, y)", but the function only explicitly returns zero in the ending
condition, so I believe this sample would return zero all the way back up the
stack. I could be wrong - I haven't tried to run the code. But that's the
easiest way to see what might happen, or to test a theory - run it and see
what happens (save your work first though - just in case).
HTH (it's late though, I'm not sure how much help it is...)
Shawn
>
> If i call Add() via a variable assignment via:
> int a;
> a = Add(4,3);
> how does the data at the end of the recursive loop make it back to 'a'?
>
> Sorry if i'm troubling any of you, but i'm starting to get a little
> stuck on this. I really should have attended tonight.
>
> Thanks in advance for any advice.
>
> -Rob
>
> Jason Louie wrote:
> >Simple recursion:
> >
> >// For integers only
> >int Add (int x, int y)
> >{
> > if (y == 0) return 0;
> >
> > if (y > 0) return (Add (x + 1, y - 1));
> > if (y < 0) return (Add (x - 1, y + 1));
> >}
> >
> >Here is an example of how the function is executed,
> >
> >Add (4, 3);
> > Add (4 + 1, 3 - 1); // y > 0 -- which is Add (5, 2);
> > Add (5, 2);
> > Add (5 + 1, 2 - 1);
> > Add (6, 1);
> > Add (6 + 1, 1 - 1);
> > Add (7, 0); // Since y is now 0 return x; (return 7)
> >
> >Hope this helps. Convert the function to a Multiply function would be
> >a good way to get a better understanding of recursion.
> >
> >On Sat, 12 Feb 2005 09:47:05 -0700, Cade Cairns <cairnsc at gmail.com> wrote:
> >>A classical example of recursion is in binary tree algorithms. They
> >>are (in various forms) one of the most useful data structures you can
> >>employ in the C language. Here is an example I found using Google:
> >>
> >>http://www.cee.hw.ac.uk/~rjp/Coursewww/Cwww/tree.html
> >>
> >>On Sat, 12 Feb 2005 01:25:25 -0700, Shawn <sgrover at open2space.com> wrote:
> >>>The simplest explanation of recursion is a function that calls itself,
> >>> and has and ending condition of some sort.
> >>>
> >>>The key is the ending condition - otherwise you essentially end up in an
> >>>endless loop, but sucking up stack space for each function call.
> >>>
> >>>Um... I'm not comfortable enough with C/C++ to create code in it, but
> >>>JavaScript is a similar syntax (if you stick with the basics), so I'll
> >>> use that to show a sample:
> >>>
> >>>---------------------
> >>>function AddTotals(CurrentIndex, Totals)
> >>>{
> >>> //End Condition
> >>> if (CurrentIndex >= 10)
> >>> {
> >>> return parseFloat(Totals) + 10;
> >>> }
> >>> else {
> >>> CurrentIndex = CurrentIndex + 1;
> >>> Totals = CurrentIndex +
> >>> parseFloat(AddTotals(CurrentIndex, Totals)); }
> >>>
> >>>//This could be a printf() function - the purpose is just so we can see
> >>> what //is happening
> >>>document.write(parseFloat(CurrentIndex) +" : " + parseFloat(Totals) +
> >>> "<br>");
> >>>
> >>> return Totals;
> >>>}
> >>>
> >>>alert(AddTotals(0,0));
> >>>---------------------
> >>>
> >>>The alert() function at the end of the snippet triggers our recursive
> >>>function, and passes in our starting values of 0 and 0.
> >>>
> >>>The first time through the loop , CurrentIndex is less than 10, so we'll
> >>>increase it by 1, and then the value of the new call to the AddTotals()
> >>>function, to our function.
> >>>
> >>>Critical points to take note of:
> >>>- all variables declared in the function have local scope - changing a
> >>> global variable in this manner can lead to some very unexpected (and
> >>> unpleasent) results, if not carefully managed.
> >>>- we have a very clear end condition - When CurrentIndex is >= 10, we
> >>> don't call the function again.
> >>>- we are updating the values used in our ending condition, so we know
> >>> we'll eventually hit it. I guess you can rely on external values for
> >>> your condition, but that's probably asking for trouble.
> >>>
> >>>The syntax might be a little different in C/C++, but the concepts, and
> >>>critical points still apply. I've yet to see a language where they
> >>> don't apply. Just be careful you're not relying on a pointer that
> >>> could potentially be updated outside the recursive function.
> >>>
> >>>Hope this helps. (btw, the code above works - I tested it first..
> >>> <grins>)
> >>>
> >>>Shawn
> >>>
> >>>On Saturday 12 February 2005 00:25, Rob S wrote:
> >>>>Doug Boyd wrote:
> >>>>>Hi guys,
> >>>>>
> >>>>>I'm working on a Javascript program to solve the classic Hanoi Towers
> >>>>>problem. The recursive function and algorithm works fine, but I'm
> >>>>> unable to write the 'textstring' variable to the <textarea>.
> >>>>
> >>>>I was wondering if someone could walk me through an explanation of
> >>>>recursion in the context of the C programming language? This is
> >>>> probably best saved for a meeting session, but seeing as the next
> >>>> meeting's a few weeks away, I was wondering if someone could try
> >>>> explaining it to me over email?
> >>
> >>_______________________________________________
> >>clug-progsig mailing list
> >>clug-progsig at clug.ca
> >>http://clug.ca/mailman/listinfo/clug-progsig_clug.ca
> >
> >_______________________________________________
> >clug-progsig mailing list
> >clug-progsig at clug.ca
> >http://clug.ca/mailman/listinfo/clug-progsig_clug.ca
>
> _______________________________________________
> clug-progsig mailing list
> clug-progsig at clug.ca
> http://clug.ca/mailman/listinfo/clug-progsig_clug.ca
More information about the clug-progsig
mailing list