前回はメソッドの関数的な使い方について説明しました。今回は再帰定義について説明します。関数定義の中で、その関数自身を呼び出すことを「再帰呼び出し (recursive call)」とか「再帰定義 (recursive definition)」といいます。
関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。ところが、再帰定義は特別なことではありません。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。もちろん Java の関数 (メソッド) も再帰呼び出しが可能です。
再帰定義というと、Lisp / Scheme のような「関数型言語」の専売特許だと思われている方もいるでしょう。実際、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックの一つと思い込んでしまい、初心者の方は避けて通ることが多いように思います。再帰定義は、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができます。
まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を図 1 に示します。
0! = 1 n! = n * (n - 1)! 図 1 : 階乗の定義
階乗の定義からわかるように、n の階乗は n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。リスト 1 を見てください。
リスト 1 : 階乗
public class Fact {
static int fact(int n) {
return n == 0 ? 1 : n * fact(n - 1);
}
public static void main(String[] args) {
for (int i = 0; i < 13; i++) {
System.out.println(i + " : " + fact(i));
}
}
}
C>java Fact 0 : 1 1 : 1 2 : 2 3 : 6 4 : 24 5 : 120 6 : 720 7 : 5040 8 : 40320 9 : 362880 10 : 3628800 11 : 39916800 12 : 479001600
関数 fact() は引数 n が 0 であれば 1 を返し、そうでなければ n * fact(n - 1) の計算結果を返します。fact() の定義で fact() 自身を呼び出しています。これが再帰呼び出しです。
階乗と同じように再帰定義で表されるアルゴリズムはたくさんあります。階乗の計算は簡単なので、再帰呼び出しを使わなくても繰り返しでプログラムできますが、再帰で定義されるアルゴリズムのなかには、繰り返しに変換すると複雑なプログラムになってしまうものがあります。
このような場合は、素直に再帰定義を使ったほうがわかりやすいプログラムになり、間違いを犯す危険性が少なくなります。難しいアルゴリズムでも、再帰定義を使うと簡単にプログラムできる場合もあるのです。
それでは、再帰定義のポイントを説明しましょう。図 2 を見てください。
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│Call:1 │->│Call:2 │->│Call:3 │->│Call:4 │->│Call:5 │
│n:4 │ │n:3 │ │n:2 │ │n:1 │ │n:0 │
│value : 24│<-│value : 6 │<-│value : 2 │<-│value : 1 │<-│value : 1 │
└─────┘ └─────┘ └─────┘ └─────┘ └─────┘
図 2 : fact の再帰呼び出し（n:引数の値, value:返り値）
図 2 は関数 fact(4) の呼び出しを表したものです。最初の呼び出し (Call:1) では、引数 n の値は 4 なので n の値を 1 減らして fact() を再帰呼び出しします。2 回目の呼び出しでは、引数 n の値に 3 が代入されます。ここで、最初に呼び出したときと、2 回目に呼び出したときでは、引数 n の値が違うことに注意してください。
関数の引数は局所変数として扱われます。第 3 回で説明したように、局所変数には有効範囲（スコープ）があります。引数の場合、その関数が実行されている間だけ有効です。局所変数は関数呼び出しが行われるたびに新しく生成されて、そこに値が代入されます。そして、関数の実行が終了すると、生成された局所変数は廃棄されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 n は名前が同じでも異なる変数になるのです。ここが再帰呼び出しを理解するポイントの一つです。
プログラムを見ると変数 n は一つしかありませんが、再帰呼び出しが行われるたびに新しい変数 n が作られていくと考えてください。fact(4) を実行しているときの n は 4 であり、fact(3) を呼び出すときには、この n の値を書き換えるのではなく、新しい変数 n を用意して、そこに 3 を代入するのです。
同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 n が 0 になります。このとき、if の then 節が実行され 1 が返されます。ここで再帰呼び出しが止まります。これを再帰呼び出しの「停止条件」といいます。ここが第 2 のポイントです。停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、Java であればプログラムの実行は途中で停止します。再帰呼び出しを使う場合は、この停止条件に十分注意してください。
fact(0) は 1 を返して fact(1) に戻ります。fact(1) を実行しているあいだ、引数 n の値は 1 です。したがって、fact(1) の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact(4) の値 24 を求めることができます。
もう一つ簡単な数値計算の例を示しましょう。負でない整数 a と b の最大公約数を求めるプログラムを「ユークリッド (Euclid) の互除法」で作ります。まず最初に、ユークリッドの互除法を説明します。
[ユークリッドの互除法] 負でない整数 a と b (a > b) で、a を b で割った余りを r とする。 このとき、a と b の最大公約数は b と r の最大公約数に等しい。
ユークリッドの互除法は簡単に証明できます。a と b の割り算を式 (1) で表します。
a = q * b + r --- (1)
ここで、a と b の最大公約数を m とすると、a = m * a', b = m * b' となります。すると、式 (1) は式 (2) で表すことができます。
m * a' = q * m * b' + r --- (2)
左辺は m で割り切れるので、右辺も m で割り切れる必要があります。q * m * b' は m で割り切れるので、r も m で割り切れることになります。つまり、m は b と r の公約数であることがわかります。b と r の最大公約数を m' とすると、式 (3) が成り立ちます。
m <= m' --- (3)
次に、b = m' * b'', r = m' * r' として式 (1) に代入すると、式 (4) が成り立ちます。
a = q * m' * b'' + m' * r' --- (4)
右辺は m' で割り切れるので、a も m' で割り切れる必要があります。つまり、m' は a と b の公約数であることがわかります。したがって、式 (5) が成り立ちます。
m' <= m --- (5)
式 (3) と (5) より m = m' となり、a と b の最大公約数は b と r の最大公約数に等しいことが証明されました。
あとは b を a とし、r を b にして同じ計算をすればいいわけです。この計算を繰り返し行うと、a と b はどんどん小さくなっていき、r = 0 になったときの b が最大公約数になります。
プログラムは再帰定義を使って簡単に作ることができます。リスト 2 を見てください。
リスト 2 : 最大公約数
public class Gcd {
// 最大公約数
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
// 最小公倍数
static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
public static void main(String[] args) {
System.out.println(gcd(42, 30));
System.out.println(gcd(15, 70));
System.out.println(lcm(5, 7));
System.out.println(lcm(14, 35));
}
}
関数 gcd() は引数 a と b の最大公約数を求めます。b が 0 の場合は a を返します。これが再帰呼び出しの停止条件になります。そうでなければ、gcd() を再帰呼び出しして、b と a % b の最大公約数を求めます。リスト 2 はユークリッドの互除法の定義をそのままプログラムしただけです。このように、再帰定義を使うと簡単にプログラムを作ることができます。
また、整数 a と b の最小公倍数 (lcm) は a * b / gcd(a, b) で求めることができます。それでは実行例を示します。
C>java Gcd 6 5 35 70
再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰 (tail recursion)」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶことがあります。末尾再帰は簡単な処理で繰り返しに変換できることが知られています。
Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰を繰り返しに変換する処理系があります。この機能を「末尾再帰最適化」といいます。なかには Scheme [*1] のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。
たとえば、階乗を計算する関数 fact() を思い出してください。リスト 1 の fact() は最後に n と fact() の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換するとリスト 4 になります。
リスト 4 : 階乗（末尾再帰）
public class FactTail {
static int factTail(int n, int a) {
return n == 0 ? a : factTail(n - 1, n * a);
}
public static void main(String[] args) {
for (int i = 0; i < 13; i++) {
System.out.println(i + " : " + factTail(i, 1));
}
}
}
C>java FactTail 0 : 1 1 : 1 2 : 2 3 : 6 4 : 24 5 : 120 6 : 720 7 : 5040 8 : 40320 9 : 362880 10 : 3628800 11 : 39916800 12 : 479001600
最後の再帰呼び出しで、factTail() の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれません。そこが再帰呼び出しの面白いところです。このプログラムでは引数 a の使い方がポイントです。
たとえば factTail(4) を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算します。このとき、計算の途中経過を引数 a に記憶しているのです。factTail() の呼び出しを図 3 に示します。
factTail(4, 1)
| factTail(3, 4)
| | factTail(2, 12)
| | | factTail(1, 24)
| | | | factTail(0, 24)
| | | | => a の値 24 を返す
| | | => 24
| | => 24
| => 24
=> 24
図 3 : factTail() の動作
引数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。
関数型言語の場合、while 文 や for 文 などの繰り返しがないプログラミング言語があります。また、論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。
ところで、最大公約数を求める関数 gcd() は末尾再帰になっています。Java は末尾再帰最適化をサポートしていないようですが、繰り返しに変換するのは簡単です。リスト 5 を見てください。
リスト 5 : 最大公約数を求める
public class GcdLoop {
static int gcdLoop(int a, int b) {
while(b > 0){
int c = a;
a = b;
b = c % b;
}
return a;
}
public static void main(String[] args) {
System.out.println(gcdLoop(42, 30));
System.out.println(gcdLoop(15, 70));
}
}
C>java GcdLoop 6 5
関数 gcdLoop() は引数 a, b の値を書き換えることで最大公約数を求めています。再帰定義を使ったリスト 2 のプログラムはユークリッドの互除法であることがすぐにわかりますが、繰り返しに変換するとプログラムは少しわかりにくくなると思います。
繰り返しは再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムが一番だと思います
それでは、再帰定義の例題として、高速なソートアルゴリズムを取り上げます。ソート (sort) は、ある規則に従ってデータを順番に並べ換える操作です。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。Java には配列をソートするメソッド sort() がありますが、私達でも簡単にプログラムすることができます。
ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。その中でもクイックソート (quick sort) は高速なソートアルゴリズムとして有名です。クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。2 つに分けた各々のグループを同様に分割して 2 つのグループに分けます。最後はグループの要素が一つになってソートが完了します。
9 5 3 7 6 4 2 8 最初の状態
9 5 3 7 6 4 2 8 7 を枢軸にして左側から 7 以上の値を探し、
L R 右側から 7 以下の値を探す。
2 5 3 7 6 4 9 8 交換する
L R
2 5 3 7 6 4 9 8 検索する
L R
2 5 3 4 6 7 9 8 交換する
L R
2 5 3 4 6 7 9 8 検索する。R と L が交差したら分割終了。
R L
[2 5 3 4 6] [7 9 8] この 2 つのグループについて再び
同様な分割を行う
図 4 : クイックソート
基準になる値のことを「枢軸 (pivot)」といいます。枢軸は要素の中から適当な値を選びます。今回は区間の真ん中にある要素を選ぶことにしましょう。図 4 を見てください。左側から枢軸 7 以上の要素を探し、左側から 7 以下の要素を探します。探索のときは枢軸が番兵 [*2] の役割を果たすので、ソート範囲外の要素を探索することはありません。見つけたらお互いの要素を交換します。探索位置が交差したら分割は終了です。
あとは同じ手順を分割した 2 つのグループに適用します。これは再帰定義を使えば簡単に実現できます。分割したグループの要素数が 1 になったときが再帰の停止条件になります。
クイックソートのプログラムをリスト 6 に示します。
リスト 6 : クイックソート
public class Sort {
static void quickSort(int[] buff, int low, int high) {
int p = buff[(low + high) / 2];
int i = low, j = high;
while (true) {
while (buff[i] < p) i++;
while (buff[j] > p) j--;
if (i >= j) break;
int temp = buff[i];
buff[i] = buff[j];
buff[j] = temp;
i++;
j--;
}
if (i - low > 1) quickSort(buff, low, i - 1);
if (high - j > 1) quickSort(buff, j + 1, high);
}
public static void main(String[] args) {
int[] a = {5, 6, 4, 7, 3, 8, 2, 9, 1};
quickSort(a, 0, 8);
for (int n: a) {
System.out.print(n + " ");
}
}
}
C>java Sort 1 2 3 4 5 6 7 8 9
関数 quickSort() の引数 buff がソートする配列、low が区間の下限値、high が区間の上限値です。quickSort() は buff の low から high までの区間をソートします。
最初に、区間の真ん中にあるデータを枢軸として選び、変数 p にセットします。次の while ループで、左側から枢軸以上の要素を探しています。ここでは枢軸以上という条件を、枢軸より小さい間は探索位置を進める、というように置き換えています。
同様に次の while ループで右側から枢軸以下の要素を探します。お互いの探索位置 i, j が交差したら分割は終了です。break 文でwhile ループから脱出します。そうでなければお互いの要素を交換します。交換したあと i と j の値を更新しておくことを忘れないでください。
そして、分割した区間に対して quickSort() を再帰呼び出しします。このとき要素数をチェックして、2 個以上ある場合に再帰呼び出しを行います。この停止条件を忘れると正常に動作しません。ご注意ください。
クイックソートは、枢軸の選び方で効率が大きく左右されます。区間の中央値を枢軸に選ぶと、区間をほぼ半分に分割することができます。この場合がいちばん効率が良く、データ数をN とすると N * log2 N に比例する時間でソートすることができます。
逆に、区間での最大値または最小値を枢軸に選ぶと、区間はその要素と残りの要素の 2 つに分割にされることになります。これが最悪の場合で、分割のたびに最大値もしくは最小値を選ぶと、実行時間は要素数の 2 乗に比例することになります。これは遅いソートアルゴリズムであるバブルソートや挿入ソートと同じです。
この問題は枢軸の選び方を工夫することで、完全ではありませんが回避することができます。区間の中からいくつかの要素を選び、その中で中央の値を持つ要素を枢軸とします。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は少なくなりますが、値を選ぶのに時間がかかってしまいます。実際には 3 つから 5 つの要素を選び、その中央値を枢軸とする場合が多いようです。
ある問題を解こうとするとき、可能性のあるパターンをすべて求めて、解の条件を満たしているか調べるしか方法がない場合があります。すべてのパターンを求めるとき、よく用いられる手法に「バックトラック法 (backtracking)」があります。
たとえば、簡単な例として迷路を考えてみましょう。ある地点 A で道が左右に分かれているとします。ここで、左の道を選んで先へ進むと、行き止まりになってしまいました。この場合は A 地点まで戻って右の道へ進まないといけません。
このように、失敗したら元に戻って別の選択枝を選ぶ、という試行錯誤を繰り返して解を見つける方法がバックトラック法なのです。バックトラック法は、いろいろな分野の問題に応用できる方法です。そして、再帰定義を使うと簡単にプログラムを作ることができます。
簡単な例題として「順列 (permutation) 」を生成するプログラムを作ってみましょう。異なる n 個の順列の総数は、n の階乗 (n!) 通りあります。たとえば 4 つの整数 1, 2, 3, 4 の順列は 24 通りあります。これをすべて求めるプログラムを作ります。最初に、繰り返しでプログラムしてみましょう。リスト 7 を見てください。
リスト 7 : 順列の生成（繰り返し版）
public class Perm0 {
public static void main(String[] args) {
int[] perm = new int [4];
boolean[] flag = new boolean [5];
// 一つ目の数字を選ぶ
for (int n1 = 1; n1 <= 4; n1++) {
if (flag[n1]) continue;
perm[0] = n1;
flag[n1] = true;
// 二つ目の数字を選ぶ
for (int n2 = 1; n2 <= 4; n2++) {
if (flag[n2]) continue;
perm[1] = n2;
flag[n2] = true;
// 三つ目の数字を選ぶ
for (int n3 = 1; n3 <= 4; n3++) {
if(flag[n3]) continue;
perm[2] = n3;
flag[n3] = true;
// 四つ目の数字を選ぶ
for (int n4 = 1; n4 <= 4; n4++) {
if (flag[n4]) continue;
perm[3] = n4;
flag[n4] = true;
// 順列を出力
for (int n: perm) {
System.out.print(n + " ");
}
System.out.println();
flag[n4] = false;
}
flag[n3] = false;
}
flag[n2] = false;
}
flag[n1] = false;
}
}
}
少々長いリストですが、やっていることは簡単です。選んだ数字は配列 perm に格納し、配列 flag に印 (true) をつけておきます。あとは flag に印がついていない数字を選んでいくだけです。数字を 4 つ選んだら順列 perm を出力します。
そして、次の順列を発生させるため、選んだ数字に対応する flag に false をセットします。選ぶ数字がなくなったならば、もう一つ前のループに後戻りします。このように、後戻りしながら数字を選んでいくことで、24 通りの順列を生成することができます。
このプログラムは 4 重のループですが、けっこうたいへんですね。もし、1 から 10 の順列を発生させるとなると、10 重のループになってしまいます。ところが、再帰定義を使うともっと簡単にプログラムを作ることができます。リスト 8 を見てください。
リスト 8 : 順列の生成（再帰版）
public class Perm1 {
static void printPerm(int[] perm) {
for (int x: perm) {
System.out.print(x + " ");
}
System.out.println();
}
static void makePerm(int n, int[] perm, boolean[] flag) {
if (n == perm.length) {
printPerm(perm);
} else {
for (int i = 1; i <= perm.length; i++) {
if (flag[i]) continue;
perm[n] = i;
flag[i] = true;
makePerm(n + 1, perm, flag);
flag[i] = false;
}
}
}
public static void main(String[] args) {
makePerm(0, new int [4], new boolean [5]);
}
}
関数 makePerm() は、1 から perm.length までの順列を生成します。考え方は繰り返し版と同じで、数字を選んで perm にセットし、flag に印 (true) をつけます。あとは印のついていない数字を選んでいけばいいのです。最初の呼び出しで 1 つの数字を選び、次の再帰呼び出しで 2 つめの数字を選びます。このように、n 重のループが n 回の再帰呼び出しに対応するわけです。
たとえば、perm.length の値が n だとします。n 番目の数字を選び順列を出力したら、n 番目の再帰呼び出しが終了し、n - 1 番目の再帰呼び出しに戻ります。その後は選んだ数字の flag の印を消して、新しい数字を選びます。もしも、選ぶ数字がなければ、n - 2 番目の再帰呼び出しに戻り、n - 2 番目の数字を選び直します。これで 1 から n までの順列をすべて生成することができます。
それでは実行してみましょう。
C>java Perm1 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1
このように 24 通りの順列をすべて求めることができます。