recursion

[Malcolm Dew-Jones]

On Thu, 30 Jan 2003, nkuipers wrote:

> Hello all,
> 
> 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.  

I wouldn't take this on faith.  Simply write down the steps of the
procedure and you'll see it works.  Or more easily, just save the
following and run it.  It will print the steps as it runs them, and why.

#!perl
sub printme
{
    my $i = $_[0];

    my $nice_indent = '  'x(10-$i);

    print $nice_indent , "printme called with $i\n";
    if ($i > 0) 
    { print $nice_indent , "$i > 0 so calling printme(",$i-1,")\n"; 
      printme($i-1); 
    }else
    { print $nice_indent , "$i == 0 so DONT call printme\n"; 
    }
    print $nice_indent , "about to run next line of the printme ",
          "called with $i\n";
    print "=> $i\n";

}
printme(7);
__END__


and sure enough, the numbers are printed in the order 0 1 2 3 4 5 6 7