use strict;
use warnings;


package swampyankee;

sub ackermann {
    no warnings 'recursion';
    my ($i, $j) = @_;
    return $j+1               if $i == 0;
    return ackermann($i-1, 1) if $j == 0;
    return ackermann($i-1, ackermann($i, $j-1));
}


package ikegami;

our %cache;

sub ackermann {
    no warnings 'recursion';
    my ($i, $j) = @_;
    my $key = pack('I2', $i, $j);
    return $cache{$key} if exists $cache{$key};
    return $cache{$key} = _ackermann($i, $j);
}

sub _ackermann {
    no warnings 'recursion';
    my ($i, $j) = @_;
    return $j+1               if $i == 0;
    return ackermann($i-1, 1) if $j == 0;
    return ackermann($i-1, ackermann($i, $j-1));
}


package main;

use Benchmark qw( cmpthese );

{
   local our $i = 3;
   local our $j = 4;
   print("ackermann(0..$i, $j)\n");

   print("\n");

   my $expected = '5|6|11|125';
   
   foreach (qw( swampyankee ikegami )) {
      printf("%-12s ", "$_:");

      my $sub = $_->can('ackermann');
      my $rv = join '|',
               map { $sub->($_, $j) } 0..$i;

      if ($rv eq $expected) {
         print("ok");
      } else {
         print("bad ($rv)");
      }
   
      print("\n");
   }

   print("\n");

  #my $pragma = 'use strict; use warnings; our ($i, $j); ';
   my $pragma = '';
   
   cmpthese(1000, {
      swampyankee => $pragma . '                       for (0..$i) { m
+y $rv = swampyankee::ackermann($_, $j); }',
      ikegami     => $pragma . 'undef %ikegami::cache; for (0..$i) { m
+y $rv =     ikegami::ackermann($_, $j); }',
   });
}
[download]