[clug-progsig] Recursion (was Javascript how to write to a <textarea>)

[Jason Louie]

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
>