f:id:shogonir:20180429121139p:plain

1. この記事の目的

プログラミング経験者って、なんだかんだでフィボナッチ数列を実装したことがありますよね。
みなさんはどのように実装しましたか？覚えてらっしゃいませんか？

僕は、とにかくフィボナッチ数列を再帰で実装して欲しくないのです。
なぜかというと、計算時間がとんでもなくかかるからです。
それがなぜなのか、この記事で説明したいと思います。

再帰に限らず、実装方法を間違うと同様の問題は起きることがあります。
数学的な計算時間も考慮して実装することはすごく大事だと思います。
対象は、グラフ理論や離散数学をご存知ない方とします。

2. フィボナッチ数列

フィボナッチ数列は、 n 項目が n-1 項目と n-2 項目の和である数列です。
詳細な説明はWikipediaに譲ります。

フィボナッチ数 - Wikipedia

Wikipediaを見てみると、フィボナッチ数列の定義に「再帰」というキーワードがでてきますね。
そのせいで実装としても再帰を使いたくなるのかもしれません。

3. 再帰で実装

この記事では Java でサンプルコードを紹介します。
フィボナッチ数列の n 項目を再帰で計算するメソッドを実装します。

public class FibonacciSeries {

    public static long calculateNthTermRecursive(int n) {
        if (n < 0) {
            return -1;
        }
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return calculateNthTermRecursive(n - 1) + calculateNthTermRecursive(n - 2);
    }
}

フィボナッチ数列の定義通りに実装しているので、綺麗なコードになりました。

4. ループで実装

再帰を用いない実装も紹介します。
ループを用いた実装です。

public class FibonacciSeries {

    public static long calculateNthTermLoop(int n) {
        if (n < 0) {
            return -1;
        }

        long current = 0;
        long next = 1;
        for (int i = 0; i < n; i++) {
            long tmp = current;
            current = next;
            next += tmp;
        }
        return current;
    }
}

long 型の変数3つを使い回すことで同じ結果になるよう実装できました。
再帰と比較して、可読性は落ちてしまいました。

5. 計算時間の違い

ではこの2つの実装で計算時間の違いを実験します。
第40項から第49項までを計算して、それにかかった時間を計測しました。

まずは再帰の方から。

n	fibonacci	sec
40	102334155	0.53
41	165580141	0.85
42	267914296	1.41
43	433494437	2.36
44	701408733	3.76
45	1134903170	6.63
46	1836311903	10.98
47	2971215073	16.22
48	4807526976	25.68
49	7778742049	41.26

再帰の方は、45項目あたりから計算時間が増え始めました。
49項目に至っては40秒近くかかっており、もはや待てる時間ではないです。

では、ループで実装した方はどうでしょうか。

n	fibonacci	sec
40	102334155	0.00
41	165580141	0.00
42	267914296	0.00
43	433494437	0.00
44	701408733	0.00
45	1134903170	0.00
46	1836311903	0.00
47	2971215073	0.00
48	4807526976	0.00
49	7778742049	0.00

ループの方は、49項目も10ms以内に計算できています。
なぜここまでの差がでてきてしまったのでしょうか。
実は再帰で実装すると、膨大な計算の無駄が生まれてしまいます。

図で説明したいと思います。
数字を丸で囲ったものが、フィボナッチ数列の n 項目を表すものとします。
例えば0をまるで囲うと、フィボナッチ数列の第0項目とします。

ループで第4項目を求めると次の図のように計算が進みます。

f:id:shogonir:20180429114330p:plain

最小限の計算で答えを求めているのが分かると思います。
一方で再帰で第4項目を求めると次の図のようになります。

f:id:shogonir:20180429112003p:plain

第2項目の計算が2回行われており、無駄が発生しているのがわかります。
今回は図にするため第4項目にしましたが、 n が1増えるたびに計算コストはほぼ倍になっていきます。
計算コストが倍々になっていくので、45項目あたりから時間が急激に増えてしまいます。

6. まとめ

このように、フィボナッチ数列の定義通りに実装すると計算コストがかかることがわかりました。
しかし、計算の流れをイメージできると無駄のない計算方法を実装することもできます。
同様に計算コストを削減できる場面は他にもあるはずなので、気をつけましょう。

shogonir blog

フィボナッチ数列は再帰で実装するな

目次