マンガで分かる Java入門講座
第8章 メソッド8-12. 再帰
再帰的に呼び出されるメソッドについて、その仕組みと挙動を紹介します。
● 再帰
「再帰（再帰呼び出し、再帰処理）」とは、あるメソッドから、そのメソッド自信を呼び出す処理です。
再帰では、適切な終了条件を用意しておかなければ、無限ループのような状態になってしまいます。
以下、再帰の例を示します。
ソースコード）再帰
package sample;
public class Sample {
public static void main(String[] args) {
up(0);
}
public static int up(int i) {
if (i < 3) {
System.out.println(i);
up(i + 1);
}
return i;
}
}
出力）再帰
0 1 2
再帰は、繰り返し処理という意味でループ処理と似ています。しかし。メソッドでは、そのメソッドごとにローカル変数が作成され、独立しています。そのため、処理毎に独立した値を保持することができ、ループ処理とは違った便利さがあります。
上記の例では、この特性は活かされていません。通常のループ処理で書いた方が適切な処理だと言えます。
以下、再帰の特性を活かした、少し複雑なプログラムを示します。
ソースコード）再帰2 文字の組み合わせを生成
package sample;
public class Sample {
public static void main(String[] args) {
System.out.println(strCmb("abc"));
}
// 文字の組み合わせを生成
public static String strCmb(String src) {
String res = ""; // 戻り値用文字列
int len = src.length(); // 文字列長
for (int i = 0; i < len; i ++) {
char c = src.charAt(i); // 対象文字
String[] bArr = {""}; // 再帰結果の組み合わせ
if (len >= 2) {
// 2文字以上の場合は
// 対象文字列以外を結合して再帰
String bck = strCmb(
src.substring(0, i) + // 前の文字列
src.substring(i + 1) // 後の文字列
);
/*
* 「"abc"」の「'b'」が対象文字の場合
* 「"a"」が前の文字列
* 「"c"」が後の文字列
*
* 「"abc"」の「'a'」が対象文字の場合
* 「""」が前の文字列
* 「"bc"」が後の文字列
*/
bArr = bck.split("\n"); // 改行で分割
}
//対象文字列と、再帰結果の組み合わせを結合
for (int j = 0; j < bArr.length; j ++) {
res += c + bArr[j] + "\n";
}
}
return res;
}
}
出力）再帰2 文字の組み合わせを生成
abc acb bac bca cab cba
作成：2013/06/02
更新：2015/08/09
[Permalink]