再帰定義
前回は「関数の定義方法」や「局所変数と大域変数」といった基本的なことを説明しました。今回は「再帰定義」を中心に関数の使い方を説明します。
関数定義の中で、その関数自身を呼び出すことを「再帰呼び出し (recursive call)」とか「再帰定義 (recursive definition)」といいます。関数定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。ところが、再帰定義は特別なことではありません。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。もちろん Perl の関数も再帰呼び出しが可能です。
●再帰定義の基本
再帰定義というと、「関数型言語」の専売特許だと思われている方もいるでしょう。実際、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックの一つと思い込んでしまい、初心者の方は避けて通ることが多いように思います。再帰定義は、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。
まずは簡単な例として、階乗を計算するプログラムを考えてみましょう。
図 : 階乗の定義
階乗の定義からわかるように、n の階乗を求めるには (n - 1) の階乗の答えがわかれば求めることができます。実は、これをそのままプログラミングすることができるのです。
リスト : 階乗を計算する (sample0601.pl)
use strict;
use warnings;
sub fact {
my $n = shift;
$n == 0 ? 1 : $n * fact($n - 1);
}
foreach my $i (0 .. 15) {
print fact($i), "\n";
}
関数 fact は引数 $n が 0 であれば 1 を返し、そうでなければ $n * fact($n - 1) の計算結果を返します。fact の定義で fact 自身を呼び出しています。これが再帰呼び出しです。
階乗と同じように再帰定義で表されるアルゴリズムはたくさんあります。階乗の計算は簡単なので、再帰呼び出しを使わなくても繰り返しでプログラムできますが、再帰で定義されるアルゴリズムのなかには、繰り返しに変換すると複雑なプログラムになってしまうものがあります。
このような場合は、素直に再帰定義を使ったほうがわかりやすいプログラムになり、間違いを犯す危険性が少なくなります。難しいアルゴリズムでも、再帰定義を使うと簡単にプログラムできる場合もあるのです。
実行結果は次のようになります。
$ perl sample0601.pl 1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800 87178291200 1307674368000
●再帰定義のポイント
それでは、このプログラムの動作を説明します。次の図を見てください。
fact に 4 を与えて呼び出してみましょう。変数 $n には 4 が代入されます。この変数 $n の値は fact(4) が実行されているあいだだけ有効です。上図では、そのことを枠で示しています。この場合、$n は 0 ではないので、else 節が実行されます。最初の枠の中を見てください。ここで $n の値から 1 引いた値で自分自身を呼び出しています。
次に、2 番目の枠の中を見てください。変数 $n には 3 が代入されます。この変数 $n は fact(4) を実行しているときの変数 $n とは違います。引数を格納する @_ や局所変数は、関数を実行するたびに新しいメモリ領域に割り当てられるのです。つまり、fact(3) を実行するときに、変数 $n に対応するメモリ領域を割り当て、そこに 3 を代入するのです。したがって、fact(4) と fact(3) の呼び出しでは、変数 $n に割り当てられているメモリは異なっているのです。ここが再帰呼び出しを理解するポイントのひとつです。
関数の呼び出しが行われると、局所変数は新しいメモリに割り当てられる
プログラムを見ると変数 $n はひとつの領域しかないように見えますが、関数を呼び出すたびに、局所変数は新しいメモリに割り当てられていくのです。したがって、fact(4) を実行しているときの $n は 4 で、fact(3) を実行しているときの $n は 3 なのです。再帰呼び出しが行われるたびに、新しい $n が作られると考えてください。
同様に fact(2), fact(1), fact(0) と順番に呼び出していきます。fact(0) の場合、$n は 0 ですから条件が成立します。ここで再帰呼び出しが止まります。ここが第 2 のポイントです。
再帰呼び出しを止める条件（停止条件）を設定すること
停止条件を作らなかったり、作ってもその条件を満たさないならプログラムは正常に動作しません。停止条件がなかったり条件を満たさない場合、関数呼び出しが限りなく行われるので、Perl 自体が停止することになるでしょう。
fact(0) は 1 を返します。実行が終了したので、変数 $n の値は元に戻ります。これも局所変数の特徴でしたね。では、どの値に戻るのでしょうか。関数を呼び出した場合、それを呼び出した関数に戻ります。この場合は fact(0) が終了したので fact(1) の実行に戻るのです。fact(1) はまだ終了していないので、引数 $n の値は 1 のままです。図でいえば、実行が終了したら枠が壊れていくと考えてください。一番内側の枠が壊れて、その前に値を代入された局所変数が顔を出すのです。
fact(0) が 1 を返してきたので、fact(1) を計算することができます。1 * 1 を計算して fact(1) は 1 を返します。同様に、順番に値を計算していき、最後に fact(4) の値を求めることができます。
●ユークリッドの互除法
もう一つ簡単な数値計算の例を示しましょう。負でない整数 a と b の最大公約数を求めるプログラムを「ユークリッド (Euclid) の互除法」で作ります。まず最初に、ユークリッドの互除法を説明します。
負でない整数 \(a, b \ (a \gt b)\) で、\(a\) を \(b\) で割った余りを \(r\) とする。
このとき、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しい。
ユークリッドの互除法は簡単に証明できます。\(a\) と \(b\) の割り算を式 (1) で表します。
ここで、\(a\) と \(b\) の最大公約数を \(m\) とすると、\(a = m \times a', \ b = m \times b'\) となります。すると、式 (1) は式 (2) で表すことができます。
左辺は \(m\) で割り切れるので、右辺も \(m\) で割り切れる必要があります。\(q \times m \times b'\) は \(m\) で割り切れるので、\(r\) も \(m\) で割り切れることになります。つまり、\(m\) は \(b\) と \(r\) の公約数であることがわかります。\(b\) と \(r\) の最大公約数を \(m'\) とすると、式 (3) が成り立ちます。
次に、\(b = m' \times b'', \ r = m' \times r' \)として式 (1) に代入すると、式 (4) が成り立ちます。
右辺は \(m'\) で割り切れるので、\(a\) も \(m'\) で割り切れる必要があります。つまり、\(m'\) は \(a\) と \(b\) の公約数であることがわかります。したがって、式 (5) が成り立ちます。
式 (3) と (5) より \(m = m'\) となり、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しいことが証明されました。
あとは b を a とし、r を b にして同じ計算をすればいいわけです。この計算を繰り返し行うと、a と b はどんどん小さくなっていき、r = 0 になったときの b が最大公約数になります。
プログラムは再帰定義を使って簡単に作ることができます。次のリストを見てください。
リスト : 最大公約数 (sample0602.pl)
use strict;
use warnings;
# 最大公約数
sub gcd {
my ($a, $b) = @_;
$b == 0 ? $a : gcd($b, $a % $b);
}
# 最小公倍数
sub lcm {
my ($a, $b) = @_;
$a * $b / gcd($a, $b);
}
print gcd(42, 30), "\n";
print gcd(15, 70), "\n";
print lcm(5, 7), "\n";
print lcm(14, 35), "\n";
関数 gcd は引数 $a と $b の最大公約数を求めます。$b が 0 の場合は $a を返します。これが再帰呼び出しの停止条件になります。そうでなければ、gcd を再帰呼び出しして、$b と $a % $b の最大公約数を求めます。gcd はユークリッドの互除法の定義をそのままプログラムしただけです。このように、再帰定義を使うと簡単にプログラムを作ることができます。また、整数 $a と $b の最小公倍数 (lcm) は $a * $b / gcd($a, $b) で求めることができます。
それでは実行してみましょう。
$ perl sample0602.pl 6 5 35 70
●累乗の計算
次は累乗を求める関数 pow を作ってみましょう。累乗は x の n 乗という x を n 回掛ける計算です。累乗は x の右上に小さく n を書くことで表されますが、ここでは Perl の演算子と同じく x ** n と書くことにします。
pow (x, y) = x ** y x ** 3 = x * x * x; x ** 4 = x * x * x * x; x ** 5 = x * x * x * x * x; 図 : 累乗の計算
今回のプログラムは、引数 x を実数、y を整数とします。単純な繰り返しでプログラムを作ると次のようになります。
リスト : 累乗 (sample0603.go)
use strict;
use warnings;
sub pow {
my ($x, $n) = @_;
my $v = 1;
while ($n-- > 0) {
$v *= $x;
}
$v;
}
print pow(2, 16), "\n";
print pow(2, 32), "\n";
print pow(2, 64), "\n";
$ perl sample0603.pl 65536 4294967296 1.84467440737096e+19
この場合、n 回の乗算が必要になります。ところが、式を変形するともっと少ない回数で求めることができます。
x ** 4 = (x ** 2) ** 2 -> 2 回
x ** 8 = (x ** 4) ** 2 -> 3 回
x ** 16 = (x ** 8) ** 2 -> 4 回
一般化すると
x ** y = (x ** (y / 2)) ** 2 （n は偶数）
x ** y = ((x ** (y / 2)) ** 2) * x （n は奇数）
図 : 累乗の高速化
階乗の計算では n を n - 1 の計算に置き換えていきますが、累乗の場合は y を y / 2 に置き換えていくことができます。y が半分になっていくので減少の度合いが大きくなり、計算回数は少なくて済みます。
それでは、この考え方をプログラムしてみましょう。x ** (y / 2) を計算する部分は、再帰を使えば簡単です。プログラムは次のようになります。
リスト : 累乗 (2)
sub pow1 {
my ($x, $y) = @_;
if ($y == 0) {
1;
} else {
my $z = &pow1($x, int($y / 2));
$y % 2 == 0 ? $z * $z : $x * $z * $z;
}
}
局所変数 $z を定義します。$z の値は $x ** int($y / 2) です。これは pow1 を再帰呼び出しすれば簡単に求めることができます。$y / 2 を int で整数化していることに注意してください。あとは、y が偶数であれば z * z を返し、奇数であれば x * z * z を返します。このように、再帰呼び出しを使って累乗を効率的に計算することができます。
●末尾再帰と繰り返し
再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰 (tail recursion)」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶことがあります。末尾再帰は簡単な処理で繰り返しに変換できることが知られています。
Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰を繰り返しに変換する処理系があります。この機能を「末尾再帰最適化」といいます。なかには Scheme [*1] のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。
たとえば、階乗を計算する関数 fact を思い出してください。fact は最後に $n と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると次のようになります。
リスト : 階乗 (末尾再帰, sample0604.pl)
use strict;
use warnings;
sub facti {
my ($n, $a) = @_;
$n == 0 ? $a : &facti($n - 1, $a * $n);
}
foreach my $i (1 .. 15) {
print &facti($i, 1), "\n";
}
$ perl sample0604.pl 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800 87178291200 1307674368000
最後の再帰呼び出しで、facti の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれませんね。そこが再帰呼び出しの面白いところだと思います。このプログラムでは引数 $a の使い方がポイントです。
たとえば facti(4) を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算します。このとき、計算の途中経過を引数 a に記憶しているのです。facti の呼び出しを下図に示します。
facti(4, 1)
| facti(3, 4)
| | facti(2, 12)
| | | facti(1, 24)
| | | | facti(0, 24)
| | | | => a の値 24 を返す
| | | => 24
| | => 24
| => 24
=> 24
図 : facti の動作
引数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。
関数型言語の中には、while文 や for文 などの繰り返しがないプログラミング言語があります。また、論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。
ところで、最大公約数を求める関数 gcd は末尾再帰になっています。Perl は末尾再帰最適化をサポートしていないようですが、繰り返しに変換するのは簡単です。次のリストを見てください。
リスト : 最大公約数を求める (sample0605.pl)
use strict;
use warnings;
sub gcdi {
my ($a, $b) = @_;
while ($b > 0) {
my $c = $a % $b;
$a = $b;
$b = $c;
}
$a;
}
print &gcdi(42, 30), "\n";
print &gcdi(15, 70), "\n";
$ perl sample0605.pl 6 5
関数 gcdi は引数 $a, $b の値を書き換えることで最大公約数を求めています。再帰定義を使ったプログラムはユークリッドの互除法であることがすぐにわかりますが、繰り返しに変換するとプログラムは少しわかりにくくなると思います。
繰り返しは再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムが一番だと思います。
●バックトラック法と再帰定義
ある問題を解こうとするとき、可能性のあるパターンをすべて求めて、解の条件を満たしているか調べるしか方法がない場合があります。すべてのパターンを求めるとき、よく用いられる手法に「バックトラック法 (backtracking)」があります。
たとえば、簡単な例として迷路を考えてみましょう。ある地点 A で道が左右に分かれているとします。ここで、左の道を選んで先へ進むと、行き止まりになってしまいました。この場合は A 地点まで戻って右の道へ進まないといけません。
このように、失敗したら元に戻って別の選択枝を選ぶ、という試行錯誤を繰り返して解を見つける方法がバックトラック法なのです。バックトラック法は、いろいろな分野の問題に応用できる方法です。そして、再帰定義を使うと簡単にプログラムを作ることができます。
●順列の生成
それでは簡単な例題として、順列を生成するプログラムを作ってみましょう。たとえば 4 つの整数 1, 2, 3, 4 の順列は次のように 24 通りあります。
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
一般に、異なる n 個の順列の総数は、n の階乗 (n!) だけあります。これを繰り返しを使ってプログラムしてみましょう。
リスト : 順列の生成 (繰り返し版, sample0606.pl)
use strict;
use warnings;
my @table = ();
my @perm = ();
for (my $i1 = 1; $i1 <= 4; $i1++) {
$table[$i1] = 1;
push @perm, $i1;
for (my $i2 = 1; $i2 <= 4; $i2++) {
unless ($table[$i2]) {
$table[$i2] = 1;
push @perm, $i2;
for (my $i3 = 1; $i3 <= 4; $i3++ ) {
unless ($table[$i3]) {
$table[$i3] = 1;
push @perm, $i3;
for (my $i4 = 1; $i4 <= 4; $i4++ ) {
unless ($table[$i4]) {
print "@perm $i4\n";
}
}
pop @perm;
$table[$i3] = 0;
}
}
pop @perm;
$table[$i2] = 0;
}
}
pop @perm;
$table[$i1] = 0;
}
少々長いリストですが、やっていることは簡単です。選んだ数字は @perm に格納し、@table に印をつけておきます。あとは @table に印がついていない数字を選んでいくだけです。print で @perm を出力したら、次の順列を発生させるため、選んだ数字を @perm から外し、@table の印を消します。これで 24 通りの順列を発生させることができます。
それでは実際に試してみましょう。
$ perl sample0606.pl 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
正常に動作していますね。
このプログラムは 4 重のループですが、けっこうたいへんですね。もし、1 から 10 の順列を発生させるとなると、10 重のループになってしまいます。ところが、再帰を使うともっと簡単にプログラムすることができます。
リスト : 順列の生成（再帰版, sample0607.pl）
use strict;
use warnings;
my @table = ();
my @perm = ();
sub make_perm {
my $n = shift;
for (my $i = 1; $i <= $n; $i++) {
unless ($table[$i]) {
push @perm, $i;
if ($n == @perm) {
print "@perm\n";
} else {
$table[$i] = 1;
make_perm($n);
$table[$i] = 0;
}
pop @perm;
}
}
}
make_perm(3);
make_perm(4);
関数 make_perm($n) は 1 から $n までの順列を生成します。考え方は繰り返し版と同じで、数字を選んで @perm にセットし、@table に印をつけます。あとは印のついていない数字を選んでいけばいいのです。最初の呼び出しで 1 つの数字を選び、次の再帰呼び出しで 2 つめの数字を選び・・・、というように、n 重のループが n 回の再帰呼び出しに対応するわけです。
n 番目の数字を選び順列を出力したら、n 番目の再帰呼び出しが終了し、n - 1 番目の再帰呼び出しに戻ります。その後は、選んだ数字を元に戻して、新しい数字を選びます。もし、選ぶ数字がなければ、n - 2 番目の再帰呼び出しに戻り、n - 2 番目の数字を選び直します。これで 1 から n までの順列をすべて生成することができます。
それでは実行してみましょう。
$ perl sample0607.pl 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 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
正常に動作していますね。
●ハノイの搭
再帰といえば、忘れてはいけないのが「ハノイの塔」です。これは棒に刺さっている円盤を、次に示す規則に従ってほかの棒に移動させるパズルです。
- 一回に一枚の円盤しか動かせない。
- 小さな円盤の上に大きな円盤を乗せることができない。
- 最初は一本の棒に、大きい円盤の上に小さな円盤が順番に刺さっている。
ハノイの塔は再帰を使えば簡単に解ける問題です。たとえば円盤 5 を A から C に移すには、その上の 4 枚の円盤を B に移しておけばいいですね。そして、円盤 5 を C に移したら、B に移した 4 枚の円盤を C に移すことを考えます。つまり、n 枚の円盤を移す問題が、n - 1 枚の円盤を移す問題へと簡単になるわけです。n - 1 枚の円盤は n - 2 枚の円盤を移す問題になり、最後は 1 枚の円盤を移す問題となります。これは簡単に解くことができますね。したがって、n 枚の円盤を A から C に移すプログラムは次のように表すことができます。
- n - 1 枚の円盤を A から B に移す
- n 枚目の円盤を A から C へ移す
- n - 1 枚の円盤を B から C へ移す
1 と 3 の手順を再帰で表せばいいわけです。これをプログラムすると、次のようになります。
リスト : ハノイの塔 (hanoi.pl)
use strict;
use warnings;
sub hanoi {
my ($n, $from, $to, $via) = @_;
if ($n == 1) {
print "$from の円盤 $n を $to へ移動\n";
} else {
hanoi($n - 1, $from, $via, $to);
print "$from の円盤 $n を $to へ移動\n";
hanoi($n - 1, $via, $to, $from);
}
}
hanoi(3, 'A', 'C', 'B');
関数 hanoi($n, $from, $to, $via) は $n 枚の円盤を $form から $to へ移します。$from, $to, $via には棒を表す文字列を与えます。円盤の番号は上図のようにつけると、変数 $n に対応させることができます。
円盤が 1 枚の場合は簡単ですね。残っている円盤を指定した棒に移します。これが再帰の停止条件になります。円盤が複数枚ある場合は、$n - 1 枚の円盤を $form から $via に移します。これは再帰を使えば簡単ですね。残った円盤 (番号は $n) を $to に移します。それから、$via にある $n - 1 枚の円盤を $to に移します。これも再帰を使えば簡単です。
それでは実行してみましょう。5 枚は多いので 3 枚の円盤を動かしてみます。
$ perl hanoi.pl A の円盤 1 を C へ移動 A の円盤 2 を B へ移動 C の円盤 1 を B へ移動 A の円盤 3 を C へ移動 B の円盤 1 を A へ移動 B の円盤 2 を C へ移動 A の円盤 1 を C へ移動
とても簡単に解くことができました。
今回はここまでです。次回は「リファレンス (reference)」の基本的な使い方をＣ言語と比較しながら説明する予定です。
改訂 2023 年 3 月 19 日