再帰アルゴリズム その2

Java

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

再帰アルゴリズム その1

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

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

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

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つの数を足し算すると、その上位の数になる数列です。

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

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

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

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

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

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

 

jp\yucchi.fibonacci.number.FibonacciNumber.java

 

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

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

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

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

fibonacci_number
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) に戻る

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

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

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

えっ?私だけ?

まぁ、いいか。

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

jp.yucchi.fibonacci.number2.FibonacciNumber2.java

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

c_1_001

Hatena タグ:

« »

Comment

  1. ゆっちのBlog » 再帰アルゴリズム その2

    返信

Trackback

  1. [...] 再帰アルゴリズム その2 [...]

  2. [...] 再帰アルゴリズム その2 [...]

  3. [...] 再帰アルゴリズム その2 [...]

Leave a Reply

* が付いている項目は、必須項目です!

次の HTML タグと属性を利用できます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*

Trackback URL