recursion

[Peter Scott]

At 01:12 PM 1/30/03 -0800, nkuipers wrote:
>In Java class today the instructor introduced recursion.  He coded up a very
>simple program expressed in pseudocode as follows:
>
>method printme with arg int
>if int not equal to 0 { printme (int-1) }
>print int
>
>The fact that this program with initial input of 7 printed 1 through 7 
>in that
>order blew my mind, and although I came to a recognition of what was
>happening, I can't say I truly understand it and certainly in a more complex
>recursion I'd be hooped.  Now, of the three concepts he told us we need to
>understand (base case, progress), the third was the oddest, and, he said, the
>trickiest, and that was simply that you have to believe it will 
>work.  He also
>said that it's critical to sit down in front of a computer and play 
>with stuff
>like this.  Since Perl is more native to my mind, I'd like to do my 
>conceptual
>playing in Perl, and then I expect it'll be fairly easy to implement these
>concepts in Java.
>
>My question then is what is the best way to approach recursion in general,
>with a slant to Perl.

I confess I am unable to fathom the modern approach to teaching 
CS.  Why they teach O-O before or instead of procedural or structured 
programming is beyond me.  Why they make it so hard to understand the 
basic concepts of stack frames and parameter passing 
likewise.  Recursion is extremely easy to understand when you look at 
it in terms of stack frames.  Why they have to make it so difficult to 
follow that you have to take it on faith is... well, you get the picture.

Here, try this:

fact(5);
sub fact {
   my $arg = shift;
   $arg < 2 and return 1;
   return $arg * fact($arg - 1);
}

Run that under the debugger and s(tep) through it, periodically hitting 
T for stack trace.

To make it a bit plainer, let's make a version that allows us to trace 
the percolation back up:

fact(5);
sub fact {
   my $arg = shift;
   $arg < 2 and return 1;
   my $res = $arg * fact($arg - 1);
   return $res;
}

Do that and in addition to s, T, do x $res when stopped at the second return.
--
Peter Scott
Pacific Systems Design Technologies
http://www.perldebugged.com/