キャッシュを使う

キャッシュとかいっても計算した値を保存しておくというだけです．Perlの場合，ハッシュで保存するのが楽です．第項を計算したら，その結果ををキーとするハッシュの値として保存しておくだけです．このハッシュをグローバル変数にしてしまっても構わないのですが，クロージャにしてしまえば，他の計算で間違って壊されるようなことはないのでクロージャにします．

{my %cache;#クロージャのハッシュ
sub fibcache{
    my $n = shift;
    return $cache{$n} if defined $cache{$n};
    return 0 if $n==0;
    return 1 if $n==1;
    return $cache{$n} = fibcache($n-1)+fibcache($n-2);
}
}

すでに計算されていればその値をそのままreturnして，そうでなければ再帰呼び出しをして，その値をキャッシュすると同時にreturnするという仕組みです．

%cacheはサブルーチンfibcacheと同じスコープ内のレキシカルな変数ですが，そのスコープを外れると見えなくなります．しかし，fibcacheとは同じスコープなのでfibcacheからは%cacheでアクセスできる，つまり，外側ぎりぎりにいるので「クロージャ」(closure）です．

これで計算すると，ものすごく早くなります．bigintを使ってフィボナッチの1000項を計算させてみると，

43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875

となって，滅茶苦茶な数ですが，計算は圧倒的に早いです．早いのは当然で，再帰で呼び出される回数が桁違いに少なくなってます．前と同じようにカウントすると

	0	1	2	3	4	5	・・・	10	・・・	20	・・・	30	・・・
(キャッシュなし)	1	1	3	5	9	15	・・・	177	・・・	21891	・・・	2692537	・・・
(キャッシュつき)	1	1	3	5	7	9	・・・	19	・・・	39	・・・	59	・・・

違いは歴然で，キャッシュが極めて有効に働いているのが分かります．