再帰アルゴリズム その１
再帰アルゴリズムについてちょっとしたメモを残しておきます。
まず再帰とは、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいうらしいです。
日本語って難しいですね。
プログラムを組む上でコーディングテクニックについては自分と同じ（自分自身）をある条件が満たされるまで呼び出し続けることのようです。
これって for 文もしくは while 文でもいけそうですね。
とりあえず非効率的かつ非現実的ではありますが 3 の階乗値を求めるプログラムを作ってみましょう。
| jp.yucchi.recursion.example.RecursionExample.java |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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) の戻り値が出力されます。
これだったらループ文でも大差ないだろうと思った あ・な・た 正解です。(^_^;
しかし、この再帰アルゴリズムは奥が深いんです。
そのことはまた今度ってことで今回はこのシンプルなプログラムの流れをデバッガを使い確認してみます。
上記のプログラムのままでもいいのですが、ちょっと解りやすくするために下記のように変更します。
| jp.yucchi.recursion.example.RecursionExample.java |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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 を確認しながらご覧ください。
どうですか？
処理が最初の呼び出し元に戻るまで追うことができましたでしょうか？
コードはすっきりとなってるけどプログラムの流れはけっこう追っていくのは大変です。
論理的に考えて組んでしまえばこのかったるい処理はコンピューターがやってくれるので非常に便利です。
今回は再帰アルゴリズムの基本中の基本のメモでした。
TAGS: Java | 2013年1月1日4:42 PM
Comment
ゆっちのBlog » 再帰アルゴリズム その２ ゆっちのBlog » ユークリッドの互除法 Euclidean Algorithm ゆっちのBlog » ハノイの塔 Tower of Hanoi ゆっちのBlog » Nクイーン問題 nQueens Problem
Trackback
2013年1月2日4:56 AM（編集）
[...] 再帰アルゴリズム その１ [...]
2013年1月3日4:58 AM（編集）
[...] 再帰アルゴリズム その１ [...]
2013年1月4日5:03 AM（編集）
[...] 再帰アルゴリズム その１ [...]
2013年1月5日6:58 AM（編集）
[...] 再帰アルゴリズム その１ [...]
Trackback URL