アルゴリズム入門(フィボナッチ数列)

フィボナッチ数列とは「直前の２つの項を足し合わせてできる数列のことで
【１，１，２，３，５，８，１３，２１・・・】
と無限に続きます。（１＋１＝２、１＋２＝３，２＋３＝５，３＋５＝８，・・・）
このフィボナッチ数列をプラグラムで求めてみましょう。
最初の2つの項の場合は１を返し、それ以外の場合には前の２つの項の和を返す、というプログラムです。

#!/usr/bin/awk -f

BEGIN{
    print fabonacci(35);
}


function fabonacci(n){
    if((n == 1) || (n == 2)){
        return 1;
    }else{
        return fabonacci(n - 2) + fabonacci(n - 1);
    }
}

これは、関数の中から自身の関数を呼び出しています。
このような書き方を「再帰」といいます。
再帰を使うと、このようなプログラムは非常にシンプルに実装できることが知られています。
ただし、処理を終わらせるために、終了条件の指定が必要です（終了条件がないと無限に処理が続いてしまう）
今回の場合は、ｎ＝１とｎ＝２のときに処理を終了するように指定しています。

wk -f fibonacci.awk 
9227465

これで求めることができますが、同じ値を何度も計算することになります。
時間が大幅にかかってしまいます。
上記の問題を解決するため、下記のように書き換えてみます。

#!/usr/bin/awk -f

BEGIN{
    memo[1] = 1;
    memo[2] = 1;
    print fibonacci(35);
}


function fibonacci(n){
    if(n in memo){
        return memo[n];
    }
    memo[n] = fibonacci(n - 2) + fibonacci(n - 1);
    return memo[n];
}

まず、memoという辞書（連想配列）に終了条件の値を入れています。
関数fibonacciの中では、memoに存在すれば値を返し、存在しなければ計算してmemoに入れます。
その上でmemoに入れた値を返します。
このように変更すると、一度計算した値は保存しておけるため、２度めは保存されている値を使うだけです。
この方法であれば、ｎ＝４０でも５０でも１００でも一瞬でも止められます。
このような手法を「メモ化」と呼びます。