再帰アルゴリズムの覚え書きの続きです。

再帰アルゴリズム　その１

今回も、非効率的かつ非現実的な例題を利用して再帰アルゴリズムを理解していきましょう。

今回はフィボナッチ数列の特定項の値を求めるプログラムです。

フィボナッチ数列とは簡単に説明すると

F1 = 1

F2 = 1

F3 = 2

　　・
　　・
　　・

Fn = F(n – 2) + F(n – 1)

ただし、n = 1 または n = 2 のとき F(n) = 1 となる数列のことである。

つまり、1, 1, 2, 3, 5, 8, … と続く数列で、 隣り合う2つの数を足し算すると、その上位の数になる数列です。

参考までに、フィボナッチ数は、ちょうど８００年前に刊行された「算盤の書」（１２０２年）の中の有名な「兎の問題」から生まれました。

これをプログラムにするにはどうしたらいいでしょうか？

数学的手法でいくか？ループ文で和を取り値を入れ替えながら？

面倒なのでここは再帰アルゴリズムを使いましょう。(^_^;

計算処理負荷が非常に大きいことは秘密にしておきましょう。（ヲヒ

とりあえずサクッと作ってみたのでデバッグ実行させてプログラムの流れを確認してみましょう。

package jp.yucchi.fibonacci.number;

/**
 *
 * @author Yucchi
 */
public class FibonacciNumber {

    private static final int TARGET = 5;
    private static int ans;

    public static void main(String[] args) {
        ans = fib(TARGET);
        System.out.println("フィボナッチ数列第 " + TARGET + " は " + ans + " です。");
    }

    private static int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        } else {
            ans = fib(n - 2) + fib(n - 1);
            return ans;
        }

    }
}

上記のプログラムをデバッグ実行させます。

変数、n , ans の値、再帰呼び出し及び処理から戻ってくる時のプログラムの流れをしっかり確認してくださいませ。

しっかり確認できましたでしょうか？

概略図を作って流れを考察してみます。

fib(5) から fib(5 – 2) そして fib(3 – 2)

処理を終え fib(5 – 2) に戻り次の fib(3 –1)

処理を終え fib(5 – 2) に戻り fib(5 – 2) の処理を終え fib(5) に戻る

そして fib(5 –1) へ、そして fib(4 – 2) へ、処理を終えて fib(5 – 1) へ戻る

次の fib(4 – 1)　へ、そして fib(3 – 2) へ、処理を終えて fib(4 – 1) へ戻る

そして fib(3 – 1) へ、処理を終えて fib(4 – 1) へ戻る、処理を終えて fib(5 – 1) へ戻る、処理を終えて fib(5) に戻る

これでやっと呼び出し元に計算処理を結果を返せるって仕組みです。

あ～、しんど　(~_~;)

再帰アルゴリズムってプログラムだとシンプルだけど流れを考えるとしんどいですね。

えっ？私だけ？

まぁ、いいか。

ちなみに再帰アルゴリズム使わないプログラムは下記のようになります。

package jp.yucchi.fibonacci.number2;

/**
 *
 * @author Yucchi
 */
public class FibonacciNumber2 {

    private static final int TARGET = 5;

    public static void main(String[] args) {
        System.out.println("フィボナッチ数列第 " + TARGET + " は " + fib(TARGET) + " です。");
    }

    private static int fib(int n) {
        int x = 1;
        int y = 1;
        for (int i = 2; i < TARGET; i++) {
            int z = x + y;
            y = x;
            x = z;
        }
        return x;
    }
}

さて、どちらが効率いいですか？

再帰アルゴリズムについてちょっとしたメモを残しておきます。

まず再帰とは、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいうらしいです。

日本語って難しいですね。

プログラムを組む上でコーディングテクニックについては自分と同じ（自分自身）をある条件が満たされるまで呼び出し続けることのようです。

これって for 文もしくは while 文でもいけそうですね。

とりあえず非効率的かつ非現実的ではありますが 3 の階乗値を求めるプログラムを作ってみましょう。

package jp.yucchi.recursion.example;

/**
 *
 * @author Yucchi
 */
public class RecursionExample {
    private static final int TARGET = 3;
    public static void main(String[] args) {
        System.out.println("n の階乗値は " + fact(TARGET) +" です。");
    }

    private static int fact(int n) {
        return n == 0 ? 1 : n * fact(n - 1);
    }
}

非常にシンプルです。

10 行目の標準出力処理の中にある fact(TARGET) メソッドで再帰メソッドを呼び出してます。

再帰メソッドが 13 行目の fact(int n) です。

14 行目から条件次第で再び呼び出されます。

全ての処理が帰ってきてから標準出力に fact(TARGET) の戻り値が出力されます。

これだったらループ文でも大差ないだろうと思った　あ・な・た　正解です。(^_^;

しかし、この再帰アルゴリズムは奥が深いんです。

そのことはまた今度ってことで今回はこのシンプルなプログラムの流れをデバッガを使い確認してみます。

上記のプログラムのままでもいいのですが、ちょっと解りやすくするために下記のように変更します。

package jp.yucchi.recursion.example;

/**
 *
 * @author Yucchi
 */
public class RecursionExample {
    private static final int TARGET = 3;
    public static void main(String[] args) {
        System.out.println("n の階乗値は " + fact(TARGET) +" です。");
    }

    private static int fact(int n) {
        int temp = n == 0 ? 1 : n * fact(n - 1);
        return temp;
    }
}

それではプログラムの流れを変数 n , temp を確認しながらご覧ください。

どうですか？

処理が最初の呼び出し元に戻るまで追うことができましたでしょうか？

コードはすっきりとなってるけどプログラムの流れはけっこう追っていくのは大変です。

論理的に考えて組んでしまえばこのかったるい処理はコンピューターがやってくれるので非常に便利です。

今回は再帰アルゴリズムの基本中の基本のメモでした。