[Linux] Bash でフィボナッチ数を求める(メモ化再帰)

フィボナッチ数を求める関数

Bash でフィボナッチ数を求めるシェルスクリプトを記述します。

フィボナッチ数列は以下のような数列です。

1 2 3 5 8 13 21 34 55 89 144 ..

フィボナッチ数列の第n項を f(n) とすると、フィボナッチ数列は以下の条件で作成できます。

• f(1) = 1
• f(2) = 2
• f(n) = f(n-1) + f(n-2)

ようするに、1つ前と2つ前のフィボナッチ数を足し合わせた数がフィボナッチ数になります。

フィボナッチ数を求める関数

再帰関数を使ってフィボナッチ数を以下のように求めることができます。

my_script.sh

#!/bin/bash

function fib {
    declare -i x=$1
    if [[ x -le 2 ]]; then
        echo "$x"
        return 0
    fi
    f1=`fib $((x-1))`
    f2=`fib $((x-2))`
    echo $((f1+f2))
}

# フィボナッチ数を1-10項までを求める
for i in {1..10}; do
    fib "$i"
done

実行すると以下のようにフィボナッチ数列を生成できます。

$ bash my_script.sh
1
2
3
5
8
13
21
34
55
89

実行結果として求まるフィボナッチ数は正しいですが、処理時間は求める数列が大きくなれば指数関数的に大きくなります。

例えば第20項を求めるとかなり体感でも時間がかかるのがわかります。私の環境だと1分30秒程度かかりました。これを効率化してみます。

メモ化再帰でフィボナッチ関数を効率化

フィボナッチ数を求める関数を メモ化再帰 と呼ばれる手法で効率化します。

フィボナッチ数を求めるとき、すでに計算済のフィボナッチ数はどこかにメモしておき再利用するようにします。

bash で利用可能な連想配列を使用して実装してみます。

#!/bin/bash

# 連想配列で計算済フィボナッチ数を管理
declare -A memo=(
    ['1']='1'
    ['2']='2'
)

function fib {
    declare -i x=$1

    # すでに計算済の場合はそれを利用する
    if [ -n "${memo[$x]}" ]; then
        echo "${memo[$x]}"
        return 0
    fi

    # 未計算のフィボナッチ数は計算
    f1=`fib $((x-1))`
    f2=`fib $((x-2))`
    let res=$f1+$f2

    # 計算結果をメモしておく
    memo["$x"]="$res"
    echo "$res"
}

for i in {1..20}; do
    fib "$i"
done

20項目まで一気に求めても以下のように0.1秒かからずに完了できます。

$ time bash my_script.sh
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946

real    0m0.089s
user    0m0.000s
sys     0m0.063s

計算量が大幅に完全されていることが分かります。

以上。

参考URL

• bashで連想配列 – Qiita
• シェルスクリプトに挑戦しよう（18）連想配列：“応用力”をつけるためのLinux再入門（38） – ＠IT