[Perl]Ackermann函数和Memoize模块

今天阅读《Perl Hacks》这本书，看到Ackermann函数和Memoize模块的介绍，才想起以前在学习递归和算法的时候曾经见过这个Ackermann，不过那时怎么也没有想到这个函数居然有如此强大的“威力”——发散得极其迅速，以至于参数稍大一点就不可能算出它的精确值。于是它经常被用作电脑的benchmark……

Ackermann函数是数学史上和计算机史上的一个经典递归函数，它的表达式并不复杂，但却几乎无法计算。其表达式如下：

A(m,n) = n+1 when m=0;
       = A(m-1,1) when n=0;
       = A(m-1,A(m,n-1)) otherwise.

用Perl语言写成代码如下：

sub ackermann {
    my ( $m, $n ) = @_;

    return $n + 1 if $m == 0;
    return ackermann( $m - 1, 1 ) if $n == 0;
    return ackermann( $m - 1, ackermann( $m, $n - 1 ) );
}

计算这个函数的值需要非常长的时间，因为该函数在 m 增加时发散得异常迅速…… 至于如何迅速大家可自行查资料（这个函数中文似乎叫做阿克曼函数）。

在Perl中，Memoize模块可以在某些程度上加速这种递归函数的运行。 Memoize模块是典型的“以空间换时间”的模块，像ackermann这种不带任何副作用并且对于给定的参数返回值也固定的函数来说，Memoize模块能记录下指定参数的函数返回值，再次调用ackermann函数时，就可以从直接使用上次记录的返回值，而不用重新计算。

通过Memoize模块运行ackermann函数的程序如下：

#!/usr/bin/perl

use strict;
use warnings;
no warnings 'recursion';

use Memoize;

memoize('ackermann');

sub ackermann {
    my ( $m, $n ) = @_;

    return $n + 1 if $m == 0;
    return ackermann( $m - 1, 1 ) if $n == 0;
    return ackermann( $m - 1, ackermann( $m, $n - 1 ) );
}

print ackermann( 3, 10 ), "\n";

该程序计算A(3,10)，如果不用Memoize模块，程序要运行至少一分钟以上（我只等了一分钟），而用了Memoize之后，可在一秒钟左右计算出结果。

另外，大家不要试图去计算A(4,3)等m=3的情况，我使用Memoize算A(4,3)算了五分钟，内存使用量达到了1.7G，仍然没算出结果。

这篇文章的知识点来自于《Perl Hacks》的 Hack#66。

charlee.li