I think a better implementation of the function (at least it runs properly for me) is:

sub A {
  BARE_BLOCK: {
    if (0 == $_[0]) {
      return 1 + $_[1];
    }
    
    @_=($_[0] - 1, $_[1] ? A($_[0], $_[1]-1) : 1);
    redo BARE_BLOCK;
  }
}
[download]

Nice, using redo to explicitly perform tail-end recursion optomization. I'm wondering if the optimizer can figure that out?

Hmm, but yours gives the wrong answer for A(3,3). (61 instead of 65536)

—John

When Perl calls a recursive function it does a huge amount of work saving state, optimizing the next time you call it, etc. For a sobering comparison, compare the implementation above with the following one where I manage a stack explicitly instead of having a stack of function calls:

sub A {
  my ($x, $y) = @_;
  my @stack = ();
  while (1) {
    if (0 == $x) {
      if (@stack) {
        $y++;
        $x = pop(@stack);
      }
      else {
        return 1 + $y;
      }
    }
    else {
      if (0 == $y) {
        $x--;
        $y = 1;
      }
      else {
        push @stack, $x-1;
        $y--;
      }
    }
  }
}
[download]

Impressed?

Sorry. Perl can't detect tail-end recursion for you. In fact Perl's handling of deep recursion is truly horrible.

As for whether my answers are right or wrong, they agree with this page...

Using 5.6.0 on Win32, I get repeated

Deep recursion on subroutine "main::A" at ack.pl line 11.
Deep recursion on subroutine "main::A" at ack.pl line 13.
[download]

Update: Yup. Add   print "A($_[0],$_[1])\n"; to the top of the function to watch it run off the rails. This is not a correct implementation of the Ackerman function.

use warnings;
use strict;

sub A {

    print "\n\nentering, \$_[0] is $_[0]\n";

    print "entering, \$_[1] is $_[1]\n";
    if ($_[1] == 0) {print "1st -- returning 0\n"; return 0  ;}
    if ($_[0] == 0) {print "2nd -- returning 2*\$_[1] ($_[1])\n"; retu
+rn 2*$_[1] }
    if ($_[1] == 1) {print "3rd -- returning 2\n"; return 2 };
    print "not returning : ";
    # figure A(m-1, A(m, n-1)) using in-place parameter list to save s
+tack
    --$_[1];
    print "\$_[1] is $_[1] ";
    
    $_[1]= &A;

    print "\$_[1] is $_[1] ";
    --$_[0];
    print "\$_[1] is $_[1] ";
    return &A;
}

print A ($ARGV[0], $ARGV[1]);
[download]

C:\>trash 3 3


entering, $_[0] is 3
entering, $_[1] is 3
not returning : $_[1] is 2

entering, $_[0] is 3
entering, $_[1] is 2
not returning : $_[1] is 1

entering, $_[0] is 3
entering, $_[1] is 1
3rd -- returning 2
$_[1] is 2 $_[1] is 2

entering, $_[0] is 2
entering, $_[1] is 2
not returning : $_[1] is 1

entering, $_[0] is 2
entering, $_[1] is 1
3rd -- returning 2
$_[1] is 2 $_[1] is 2

entering, $_[0] is 1
entering, $_[1] is 2
not returning : $_[1] is 1

entering, $_[0] is 1
entering, $_[1] is 1
3rd -- returning 2
$_[1] is 2 $_[1] is 2

entering, $_[0] is 0
entering, $_[1] is 2
2nd -- returning 2*$_[1] (
$_[1] is 4 $_[1] is 4

entering, $_[0] is -1
entering, $_[1] is 4
not returning : $_[1] is 3

entering, $_[0] is -1
entering, $_[1] is 3
not returning : $_[1] is 2

entering, $_[0] is -1
entering, $_[1] is 2
not returning : $_[1] is 1

entering, $_[0] is -1
entering, $_[1] is 1
3rd -- returning 2
$_[1] is 2 $_[1] is 2

entering, $_[0] is -2
entering, $_[1] is 2
not returning : $_[1] is 1
[download]

    if ($_[0] <= 0) {print "2nd -- returning 2*\$_[1] ($_[1])\n"; retu
+rn 2*$_[1] }
[download]

update AHA!
you appear to be implementing the algorithm incorrectly, if I may be so bold :-)

The hackery with the short-circuit sub calls is part of the problem. If I rewrite this in a "naive" way:

sub A
{
    my ($m, $n) = @_;
    return 0    if $n == 0; 
    return 2*$n if $n >  0 and $m == 0;
    return 2    if $n == 1 and $m >  0;
    A($m-1, A($m, $n-1));
}

print A ($ARGV[0], $ARGV[1]), "\n";
[download]

It's a meditation because I don't need an answer to a specific problem to accomplish some task. Rather, I just thought it was interesting and enlightening.

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?