#! perl -slw
use strict;
use Benchmark qw[ cmpthese ];
use Memoize;
no warnings 'recursion';

sub Ack1 {
    my( $M, $N ) = @_;
    return $N + 1           if $M == 0;
    return Ack1( $M - 1, 1 ) if $N == 0;
    return Ack1( $M - 1, Ack1( $M, $N - 1 ) );
}

sub Ack2 {
    my( $M, $N ) = @_;
    return $N + 1           if $M == 0;
    return Ack2( $M - 1, 1 ) if $N == 0;
    return Ack2( $M - 1, Ack2( $M, $N - 1 ) );
}
memoize( 'Ack2' );

my %memo;
sub Ack3 {
    my( $M, $N ) = @_;
    return $memo{ "$M:$N" } //= $N + 1            if $M == 0;
    return $memo{ "$M:$N" } //= Ack3( $M - 1, 1 ) if $N == 0;
    return $memo{ "$M:$N" } //= Ack3( $M - 1, Ack3( $M, $N - 1 ) );
}

our( $M, $N ) = @ARGV;

cmpthese -1, {
    nomemo   => q[ Ack1( $M, $N ) ],
    Memoise  => q[ Ack2( $M, $N ) ],
    Homebrew => q[ Ack3( $M, $N ) ],
};

__END__
C:\test>ack 3 5
             Rate   nomemo  Memoise Homebrew
nomemo     34.8/s       --    -100%    -100%
Memoise  189639/s  544863%       --     -79%
Homebrew 889629/s 2556412%     369%       --