As I suspected that your program might be getting into an infinite loop, I have modified it slightly to display the iteration number, and the $i and $j variables, and to stop it after 40 iterations:
use strict;
use warnings;
my ($i, $j) = @ARGV;
my $acker = ackermann($i, $j);
print "A($i,$j) = $acker\n";
my $iter = 0;
sub ackermann{
$iter ++;
my $i = shift;
my $j = shift;
print "Iteration $iter: i = $i, j = $j \n";
return if $iter >= 40;
if($i == 1){
undef $i;
return 2**$j;
}
elsif($j==1){
undef $j;
return ackermann($i-1,2);
}
else{
return ackermann($i-1, ackermann($i,$j-1));
}
}
I obtain the following results:
$ perl pseudo_acker.pl 3 4
Iteration 1: i = 3, j = 4
Iteration 2: i = 3, j = 3
Iteration 3: i = 3, j = 2
Iteration 4: i = 3, j = 1
Iteration 5: i = 2, j = 2
Iteration 6: i = 2, j = 1
Iteration 7: i = 1, j = 2
Iteration 8: i = 1, j = 4
Iteration 9: i = 2, j = 16
Iteration 10: i = 2, j = 15
Iteration 11: i = 2, j = 14
Iteration 12: i = 2, j = 13
Iteration 13: i = 2, j = 12
Iteration 14: i = 2, j = 11
Iteration 15: i = 2, j = 10
Iteration 16: i = 2, j = 9
Iteration 17: i = 2, j = 8
Iteration 18: i = 2, j = 7
Iteration 19: i = 2, j = 6
Iteration 20: i = 2, j = 5
Iteration 21: i = 2, j = 4
Iteration 22: i = 2, j = 3
Iteration 23: i = 2, j = 2
Iteration 24: i = 2, j = 1
Iteration 25: i = 1, j = 2
Iteration 26: i = 1, j = 4
Iteration 27: i = 1, j = 16
Iteration 28: i = 1, j = 65536
Iteration 29: i = 1, j = inf
Iteration 30: i = 1, j = inf
Iteration 31: i = 1, j = inf
Iteration 32: i = 1, j = inf
Iteration 33: i = 1, j = inf
Iteration 34: i = 1, j = inf
Iteration 35: i = 1, j = inf
Iteration 36: i = 1, j = inf
Iteration 37: i = 1, j = inf
Iteration 38: i = 1, j = inf
Iteration 39: i = 1, j = inf
Iteration 40: i = 1, j = inf
So, this is seemingly never going to end (or, rather, it will fail when you will have exhausted your memory). Trying to set $i or $j to 0, rather than undefining them, when they reach 1 yields the same result. I don't have time right now to try to figure out whether your so-called Ackermann formula is necessarily going to lead you to that or whether there is a bug somewhere in your code. I might look at it later. But I suspect that this line of code:
return 2**$j;
is probably not what you really want, as it is bound to explode when $i reaches 1.
I'd suggest that you might want to use the real standard Ackermann function, which is something like this:
sub acker {
my ($m, $n) = @_;
return $n + 1 if $m ==0;
return acker( $m-1, 1) if $n == 0;
return acker ($m - 1, acker ($m, $n - 1));
}
But don't call it for the first of the two values larger than 3.
Or maybe you should give us the mathematical description of your so-called Ackermann function, so that we might understand what is probably wrong in your code.
|