覚えたら書く

IT関係のデベロッパとして日々覚えたことを書き残したいです。twitter: @yyoshikaw

フィボナッチ数を扱う - 再帰呼出し

Java プログラミング

再帰についてのメモがてらフィボナッチ数（フィボナッチ数列）をJavaでサンプル的に扱ってみました。


フィボナッチ数 (フィボナッチ数列）

n番目のフィボナッチ数を F_{n} で表すと、

\begin{align} F_{0} = 0 \end{align}

\begin{align} F_{1} = 1 \end{align}

\begin{equation} F_{n+2} = F_{n+1} + F_{n} \, \, \,(n\geqq2) \end{equation}

と定義される漸化式です。

この数列はフィボナッチ数列（Fibonacci sequence）と呼ばれています。

数列は、 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584 …と続きます。

最初の二項は 0, 1 で、以後はその直前の2つの項の和となっています。


単純に再帰で表現

フィボナッチ数を求める処理を、上記の定義に従ってJavaプログラムで表現すると、
以下のようなfibメソッドのような再帰呼び出しを利用する形になります。

public class Fibonacci1 {

    private static int fib(int num) {
        if (num == 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        return fib(num - 1) + fib(num - 2);
    }

}


実行してみましょう（n=10 に対するフィボナッチ数を求めています。実行時間も確認しています。

public class Fibonacci1 {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int n = 10;
        int sum = fib(n);

        long end = System.currentTimeMillis();
        System.out.printf("Fibonacci1 fib: (%d) -> %d \ntime: %d(ms)\n", n, sum, (end - start));
    }

    private static int fib(int num) {
        if (num == 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        return fib(num - 1) + fib(num - 2);
    }

}

実行結果

Fibonacci1 fib: (10) -> 55 
time: 0(ms)

結果もあってるようです。


計算が終わらない

同じfibメソッドの引数を n = 45 （上記コード内のnの値を45）にして実行してみました。

実行結果

Fibonacci1 fib: (45) -> 1134903170 
time: 5145(ms)

結果は出力されましたが、n = 10 の時に比べるとかなり時間がかかるようになってきました。


n = 50 （上記コード内のnの値を50に）して実行してみました。

うちのマシンでは処理が終わりませんでした・・・・
計算量が増えすぎてしまって重くなってしまったようです。


メモ化

再起処理の中で同じ n に対する計算を毎回実行してしまっているので計算量が増大してしまっているようです。
一度計算し終わった n に対する計算結果はMapにキャッシュするようにします（いわゆるメモ化）。

こういう時に便利なのが、Map#computeIfAbsent ですね。
対象のkeyに対する値が存在しない場合に、引数の処理を実行してMapに値を格納します。（戻り値は格納した値です）

import java.util.HashMap;
import java.util.Map;

public class Fibonacci2 {

    // n に対するフィボナッチ数Fnを格納するためのマップ
    // n = 0 と n = 1 に対する結果は定義に従って最初から格納
    private static final Map<Integer, Long> FIB_MAP = new HashMap<>();
    static {
        FIB_MAP.put(0, 0L);
        FIB_MAP.put(1, 1L);
    }

    private static long fib(int num) {
        // まだ値がMapに入っていなければ計算を行う
        return FIB_MAP.computeIfAbsent(num, i -> fib(num - 1) + fib(num - 2));
    }

}


では、改めて n = 50 で実行してみます。

import java.util.HashMap;
import java.util.Map;

public class Fibonacci2 {

    // n に対するフィボナッチ数Fnを格納するためのマップ
    private static final Map<Integer, Long> FIB_MAP = new HashMap<>();
    static {
        FIB_MAP.put(0, 0L);
        FIB_MAP.put(1, 1L);
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int n = 50;
        long sum = fib(n);

        long end = System.currentTimeMillis();
        System.out.printf("Fibonacci2 fib: (%d) -> %d \ntime: %d(ms)\n", n, sum, (end - start));

    }

    private static long fib(int num) {
        return FIB_MAP.computeIfAbsent(num, i -> fib(num - 1) + fib(num - 2));
    }

}

実行結果

Fibonacci2 fib: (50) -> 12586269025 
time: 55(ms)

処理が終わるまでの時間も問題なし、結果もあっています。


桁があふれた

処理時間に問題も無しなので、n = 105 （上記コード内のnの値を105）にして実行してみました。

Fibonacci2 fib: (105) -> -742723093263328478 
time: 59(ms)

あれ？結果が負数になってる・・。longの範囲では既に桁あふれしてるようです。

桁あふれ の件は、フィボナッチ数とか再帰と直接的な関係性はないとは思いますが、
まともな結果を扱えないのでは問題ありなので、扱う型をBigIntegerに変更しました。

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class Fibonacci3 {

    private static final BigInteger ZERO = BigInteger.ZERO;
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger TWO = ONE.add(ONE);

    private static final Map<BigInteger, BigInteger> FIB_MAP = new HashMap<>();
    static {
        FIB_MAP.put(ZERO, ZERO);
        FIB_MAP.put(ONE, ONE);
    }

    private static BigInteger fib(BigInteger num) {
        return FIB_MAP.computeIfAbsent(num, key -> fib(num.subtract(ONE)).add(fib(num.subtract(TWO))));
    }

}

(BigInteger では四則演算をメソッドで記述しないといけないので、コードが若干見づらくなった気がします。。。)


あらためて n = 105 で実行してみます。

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class Fibonacci3 {

    private static final BigInteger ZERO = BigInteger.ZERO;
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger TWO = ONE.add(ONE);

    private static final Map<BigInteger, BigInteger> FIB_MAP = new HashMap<>();
    static {
        FIB_MAP.put(ZERO, ZERO);
        FIB_MAP.put(ONE, ONE);
    }


    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int n = 105;
        BigInteger sum = fib(BigInteger.valueOf(n));

        long end = System.currentTimeMillis();
        System.out.printf("Fibonacci3 fib: (%d) -> %d \ntime: %d(ms)\n", n, sum, (end - start));

    }

    private static BigInteger fib(BigInteger num) {
        return FIB_MAP.computeIfAbsent(num, key -> fib(num.subtract(ONE)).add(fib(num.subtract(TWO))));
    }

}

実行結果

Fibonacci3 fib: (105) -> 3928413764606871165730 
time: 56(ms)

桁あふれなく値がもとめられました。


スタックオーバーフロー

n の値をさらに大きくして計算してみます。

n = 1000 で実行してみると、、、

実行結果

Fibonacci3 fib: (1000) -> 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875 
time: 62(ms)

計算できてそうです。


ではでは、次は　n = 1800 で実行。

それっ。

実行結果

Exception in thread "main" java.lang.StackOverflowError
    at java.math.BigInteger.compareMagnitude(BigInteger.java:3541)
    at java.math.BigInteger.subtract(BigInteger.java:1434)
    at sandobox.fibonacci.Fibonacci3.lambda$fib$0(Fibonacci3.java:33)
    at java.util.HashMap.computeIfAbsent(HashMap.java:1127)
    at sandobox.fibonacci.Fibonacci3.fib(Fibonacci3.java:33)
（以下省略）

なんとまぁ、StackOverflowErrorがスローされてしまいました。
再帰呼び出しで、コールスタックの上限をついてしまったようです。

さて、どうしたものか。


フィボナッチ数列の各項を順に計算

フィボナッチ数は以下定義な訳なので、

\begin{equation} F_{n+2} = F_{n+1} + F_{n} \, \, \,(n\geqq2) \end{equation}

基本的に数列の前２項の値がもとまっていれば、その和を計算すれば F_{n} のフィボナッチ数も導き出せます。
というわけでフィボナッチ数列を順に計算してキャッシュしていけば、求めたいフィボナッチ数を算出する際にスタックオーバーフローとなることも防げそうです。

n = 1800 に対するフィボナッチ数を求めようとしているのが、以下のコードです。
InsStream.rangeで0, 1, 2 ... と順番に n を与えてフィボナッチ数を計算してMapにキャッシュし、最終的に求めたい n に対するフィボナッチ数を計算しています。

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;

public class Fibonacci3B {

    private static final BigInteger ZERO = BigInteger.ZERO;
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger TWO = ONE.add(ONE);

    private static final Map<BigInteger, BigInteger> FIB_MAP = new HashMap<>();
    static {
        FIB_MAP.put(ZERO, ZERO);
        FIB_MAP.put(ONE, ONE);
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int n = 1800;
        IntStream.range(1, n)
                .forEach(i -> fib(BigInteger.valueOf(i)));

        BigInteger sum = fib(BigInteger.valueOf(n));

        long end = System.currentTimeMillis();
        System.out.printf("Fibonacci3 fib(%d) -> %d\ntime: %d(ms)\n", n, sum, (end - start));

    }

    private static BigInteger fib(BigInteger num) {
        return FIB_MAP.computeIfAbsent(num, key -> fib(num.subtract(ONE)).add(fib(num.subtract(TWO))));
    }
    
}

実行結果

Fibonacci3 fib(1800) -> 6733912172802933472606353001846945074658287378884326089477601632746080275952604203199580265153593862390858117766432295498560989719530281829452850286454536277301941625978000791367655413469297462257623927534855511388238610890658838439857922737938956952361558179389004339772497124977152035343580348215676156404424782380266118900316342135562815217465023272599528784782167145877600
time: 62(ms)

スタックオーバーフローも発生せず、値を求めることができたようです。
（値でかすぎて正しいのか一見よくわかんないですね。。。）


まとめ

最終的に、とりあえず大きな数のフィボナッチ数も扱えるようになりました
（正直、最終的なやり方が綺麗なやり方なのかよくわかりませんが・・・）
再帰呼び出しとスタックオーバーフローに関しては、 末尾再帰呼び出し 等のキーワードが付いて回りますが、その辺は理解してないので、とりあえず今回は置いておきます。