フィボナッチの呼び出し回数を数えてみる

Perl

単純な再帰でフィボナッチを計算させると，とても時間がかかります．

my $count;
sub fib1{
    my $n = shift;
    $count++;
    return 0 if $n==0;
    return 1 if $n==1;
    return fib1($n-1)+fib1($n-2);
}

なんてすれば，fib1が何回呼ばれるか数えることもできますが，ここでは最初の明示的な呼び出しも回数に含めることにして，fib1(n)では$F_n$回呼ばれるとします

  • fib1(0)では1回（$F_0=1$）
  • fib1(1)では1回（$F_1=1$）
  • fib1(2)=fib1(1)+fib1(0)なので，最初の呼び出しもいれて1+1+1=3回（$F_2=3$）
  • fib1(3)=fib1(2)+fib1(1)なので，$F_3=F_2+F_1+1$で5回
  • ・・・
  • fib1(n)=fib1(n-1)+fib(n-2)なので，$F_n=F_{n-1}+F_{n-2}+1$回

これは，$A_n=F_n+1$とおけば，$A_n=A_{n-1}+A_{n-2}$で，$A_1=F_1+1=2$，$A_0=F_0+1=2$なので，やはり一種のフイボナッチです．一般項も容易に求められるでしょう．

$n$ 0 1 2 3 4 5 ・・・ 10 ・・・ 20 ・・・ 30 ・・・
$F_n$ 1 1 3 5 9 15 ・・・ 177 ・・・ 21891 ・・・ 2692537 ・・・

最初の単純なカウントアップで数えてみました．漸化式で計算させてもよいでしょうが，これだけ中で呼ばれていたら遅いのも当然です．しかも，ほとんどが重複した計算です．そこで計算結果を「使いまわす」のが，HOPで使われている「キャッシュ」です．