The idea was that Perl is different than pure-compiled languages like C, and (1) should not have the same limit to stack size since the Perl stack != the asm stack, and (2) I can use the old & construct to not push arguments in the recursive calls. I had also planned to try it with memoize, to look at the speed/memory difference.

But it goes boom. I think it's a bug if the perl executable hits a stray pointer, instead of giving a proper "out of memory" message.

—John

But this routine sets up an infinite loop as far as I can tell. When I added a quick print "$_[0],$_[1]" to the beginning of the sub, the output led me to believe the problem here is the algorithm itself, not the technique used to save stack space. Am I missing something?

Could be. I think the first recursive call messes up the left argument, since the stack trick basically makes them "static" variables. So that technique doesn't work for multiple recursive calls...owell. That's just one of the sinister things about this function. For the same reason, it won't "tail-end" optomize out the recursion.

sub A
 {
 return 0  if $_[1] == 0; 
 return 2*$_[1]  if $_[0] == 0;
 return 2  if $_[1] == 1;
 my $mm= $_[0]-1;
 --$_[1];
 $_[1]= &A;
 $_[0]= $mm;
 return &A;
 }
[download]

That gives the right answer for A(3,3), but blows up with reading from a bad memory location on A(4,3).