はじめに
前回は正規表現を中心に文字列処理について説明しました。今回は再帰定義について説明します。
関数定義の中で、その関数自身を呼び出すことを「再帰呼び出し (recursive call)」とか「再帰定義 (recursive definition)」といいます。関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。ところが、再帰定義は特別なことではありません。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。もちろん Ruby の関数 (メソッド) も再帰呼び出しが可能です。
●再帰定義の基本
再帰定義というと、Lisp / Scheme のような「関数型言語」の専売特許だと思われている方もいるでしょう。実際、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックの一つと思い込んでしまい、初心者の方は避けて通ることが多いように思います。再帰定義は、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができます。
まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を図 1 に示します。
図 1 : 階乗の定義
階乗の定義からわかるように、n の階乗は n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。リスト 1 を見てください。
リスト 1 : 階乗 def fact(n) return 1 if n == 0 n * fact(n - 1) end # 別解 def fact(n) = n == 0 ? 1 : n * fact(n - 1)
関数 fact() は引数 n が 0 であれば 1 を返し、そうでなければ n * fact(n - 1) の計算結果を返します。fact() の定義で fact() 自身を呼び出しています。これが再帰呼び出しです。
階乗と同じように再帰定義で表されるアルゴリズムはたくさんあります。階乗の計算は簡単なので、再帰呼び出しを使わなくても繰り返しでプログラムできますが、再帰で定義されるアルゴリズムのなかには、繰り返しに変換すると複雑なプログラムになってしまうものがあります。
このような場合は、素直に再帰定義を使ったほうがわかりやすいプログラムになり、間違いを犯す危険性が少なくなります。難しいアルゴリズムでも、再帰定義を使うと簡単にプログラムできる場合もあるのです。
なお、Ruby 3.0 では別解のように三項演算子を使って 1 行で関数を定義することもできます。
●再帰定義のポイント
それでは、再帰定義のポイントを説明しましょう。図 2 を見てください。
図 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 のポイントです。
停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、Ruby であればプログラムの実行は途中で停止します。再帰呼び出しを使う場合は、この停止条件に十分注意してください。
fact(0) は 1 を返して fact(1) に戻ります。fact(1) を実行している間、引数 n の値は 1 です。したがって、fact(1) の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact(4) の値 24 を求めることができます。
●ユークリッドの互除法
もう一つ簡単な数値計算の例を示しましょう。負でない整数 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 が最大公約数になります。
プログラムは再帰定義を使って簡単に作ることができます。リスト 2 を見てください。
リスト 2 : 最大公約数 def gcd(a, b) return a if b == 0 gcd(b, a % b) end # 別解 def gcd(a, b) = b == 0 ? a : gcd(b, a % b)
関数 gcd() は引数 a と b の最大公約数を求めます。b が 0 の場合は a を返します。これが再帰呼び出しの停止条件になります。そうでなければ、gcd() を再帰呼び出しして、b と a % b の最大公約数を求めます。リスト 2 はユークリッドの互除法の定義をそのままプログラムしただけです。このように、再帰定義を使うと簡単にプログラムを作ることができます。
それでは実行例を示しましょう。
irb> gcd 42, 30 => 6 irb> gcd 15, 70 => 5
最小公倍数は最大公約数を使って簡単に求めることができます。リスト 3 を見てください。
リスト 3 : 最大公倍数 def lcm(a, b) a * b / gcd(a, b) end # 別解 def lcm(a, b) = a * b / gcd(a, b)
整数 a と b の最小公倍数は a * b / gcd(a, b) で求めることができます。実行例を示します。
irb> lcm 5, 7 => 35 irb> lcm 14, 35 => 70
●末尾再帰と繰り返し
再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶことがあります。末尾再帰は簡単な処理で繰り返しに変換できることが知られています。
Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰を繰り返しに変換する処理系があります。この機能を「末尾再帰最適化」[*1] といいます。なかには Scheme [*2] のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。
たとえば、階乗を計算する関数 fact() を思い出してください。リスト 1 の fact() は最後に n と fact() の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換するとリスト 4 になります。
リスト 4 : 階乗（末尾再帰） def facti(n, a = 1) return a if n == 0 facti(n - 1, a * n) end # 別解 def facti(n, a = 1) = n == 0 ? 1 : facti(n - 1, a * n)
最後の再帰呼び出しで、facti() の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれません。そこが再帰呼び出しの面白いところです。このプログラムでは引数 a の使い方がポイントです。
たとえば facti(4) を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算します。このとき、計算の途中経過を引数 a に記憶しているのです。facti() の呼び出しを図 3 に示します。
facti(4, 1) | facti(3, 4) | | facti(2, 12) | | | facti(1, 24) | | | | facti(0, 24) | | | | => a の値 24 を返す | | | => 24 | | => 24 | => 24 => 24 図 3 : facti() の動作
引数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。
関数型言語の場合、while文 や for文 などの繰り返しがないプログラミング言語があります。また、論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。
ところで、最大公約数を求める関数 gcd() は末尾再帰になっています。Ruby はデフォルトでは末尾再帰最適化を行っていませんが [*3]、繰り返しに変換するのは簡単です。リスト 5 を見てください。
リスト 5 : 最大公約数を求める
def gcdi(a, b)
while b > 0
a, b = b, a% b
end
a
end
関数 gcdi() は引数 a, b の値を書き換えることで最大公約数を求めています。再帰定義を使ったリスト 2 のプログラムはユークリッドの互除法であることがすぐにわかりますが、繰り返しに変換するとプログラムは少しわかりにくくなると思います。
繰り返しは再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムがいちばんです
[*1] 末尾再帰最適化は一般的な呼び方で、厳密には「末尾呼び出し最適化」とか「末尾最適化」といいます。詳しい説明は拙作のページ 番外編 継続渡しスタイル の Appendix:末尾再帰と繰り返し をお読みください。
[*2] Scheme は Lisp の方言の一つです。Scheme は Lisp の標準である Common Lisp よりもシンプルな仕様で、熱心なユーザが多いプログラミング言語です。
[*3] 末尾呼び出し最適化 によると、RubyVM のオプション設定を変更すると、末尾再帰最適化を有効にすることができるそうです。
●クイックソート
それでは、再帰定義の例題として、高速なソートアルゴリズムを取り上げます。ソート (sort) は、ある規則に従ってデータを順番に並べ換える操作です。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。Ruby には配列をソートするメソッド 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 以下の要素を探します。探索のときは枢軸が番兵 [*4] の役割を果たすので、ソート範囲外の要素を探索することはありません。見つけたらお互いの要素を交換します。探索位置が交差したら分割は終了です。
あとは同じ手順を分割した 2 つのグループに適用します。これは再帰定義を使えば簡単に実現できます。分割したグループの要素数が 1 になったときが再帰の停止条件になります。
[*4] 条件を満たす要素をあらかじめ配列に入れておく方法を「番兵 (sentinel)」といいます。また、要素そのものを番兵とか番人と呼びます。
●クイックソートのプログラム
クイックソートのプログラムをリスト 6 に示します。
リスト 6 : クイックソート
def quick_sort(buff, low, high)
p = buff[(low + high)/2]
i = low
j = high
while true
i += 1 while buff[i] < p
j -= 1 while buff[j] > p
break if i >= j
temp = buff[i]
buff[i] = buff[j]
buff[j] = temp
i += 1
j -= 1
end
quick_sort(buff, low, i - 1) if i - low > 1
quick_sort(buff, j + 1, high) if high - j > 1
end
関数 quick_sort() の引数 buff がソートする配列、low が区間の下限値、high が区間の上限値です。quick_sort() は buff の low から high までの区間をソートします。
最初に、区間の真ん中にあるデータを枢軸として選び、変数 p にセットします。次の while ループで、左側から枢軸以上の要素を探しています。ここでは枢軸以上という条件を、枢軸より小さい間は探索位置を進める、というように置き換えています。
同様に次の while ループで右側から枢軸以下の要素を探します。お互いの探索位置 i, j が交差したら分割は終了です。break 文でwhile ループから脱出します。そうでなければお互いの要素を交換します。交換したあと i と j の値を更新しておくことを忘れないでください。
そして、分割した区間に対して quick_sort() を再帰呼び出しします。このとき要素数をチェックして、2 個以上ある場合に再帰呼び出しを行います。この停止条件を忘れると正常に動作しません。ご注意ください。
それでは実際に実行してみましょう。
irb> a = [5, 9, 1, 8, 2, 7, 3, 6, 4] => [5, 9, 1, 8, 2, 7, 3, 6, 4] irb> quick_sort a, 0, 8 => nil irb> a => [1, 2, 3, 4, 5, 6, 7, 8, 9] irb> b = ["foo", "bar", "baz", "abc", "def"] => ["foo", "bar", "baz", "abc", "def"] irb> quick_sort b, 0, 4 => nil irb> b ["abc", "bar", "baz", "def", "foo"]
このように、quick_sort() は数値だけではなく、比較演算子で大小関係を比較できるデータであればソートすることができます。
●クイックソートの欠点
クイックソートは、枢軸の選び方で効率が大きく左右されます。区間の中央値を枢軸に選ぶと、区間をほぼ半分に分割することができます。この場合がいちばん効率が良く、データ数をN とすると N * log2 N に比例する時間でソートすることができます。
逆に、区間での最大値または最小値を枢軸に選ぶと、区間はその要素と残りの要素の 2 つに分割にされることになります。これが最悪の場合で、分割のたびに最大値もしくは最小値を選ぶと、実行時間は要素数の 2 乗に比例することになります。これは遅いソートアルゴリズムであるバブルソートや挿入ソートと同じです。
この問題は枢軸の選び方を工夫することで、完全ではありませんが回避することができます。区間の中からいくつかの要素を選び、その中で中央の値を持つ要素を枢軸とします。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は少なくなりますが、値を選ぶのに時間がかかってしまいます。実際には 3 つから 5 つの要素を選び、その中央値を枢軸とする場合が多いようです。
●バックトラック法と再帰定義
ある問題を解こうとするとき、可能性のあるパターンをすべて求めて、解の条件を満たしているか調べるしか方法がない場合があります。すべてのパターンを求めるとき、よく用いられる手法に「バックトラック法 (backtracking)」があります。
たとえば、簡単な例として迷路を考えてみましょう。ある地点 A で道が左右に分かれているとします。ここで、左の道を選んで先へ進むと、行き止まりになってしまいました。この場合は A 地点まで戻って右の道へ進まないといけません。
このように、失敗したら元に戻って別の選択枝を選ぶ、という試行錯誤を繰り返して解を見つける方法がバックトラック法なのです。バックトラック法は、いろいろな分野の問題に応用できる方法です。そして、再帰定義を使うと簡単にプログラムを作ることができます。
●順列の生成
簡単な例題として「順列 (permutation)」を生成するプログラムを作ってみましょう。異なる n 個の順列の総数は、n の階乗 (n!) 通りあります。たとえば 4 つの整数 1, 2, 3, 4 の順列は 24 通りあります。これをすべて求めるプログラムを作ります。最初に、繰り返しでプログラムしてみましょう。リスト 7 を見てください。
リスト 7 : 順列の生成（繰り返し版）
def make_perm
perm = []
# 1 番目の数字を選ぶ
for a in 1 .. 4
perm.push a
# 2 番目の数字を選ぶ
for b in 1 .. 4
next if perm.member? b
perm.push b
# 3 番目の数字を選ぶ
for c in 1 .. 4
next if perm.member? c
perm.push c
# 4 番目の数字を選ぶ
for d in 1 .. 4
next if perm.member? d
perm.push d
print perm, "\n"
perm.pop
end
perm.pop
end
perm.pop
end
perm.pop
end
end
少々長いリストですが、やっていることは簡単です。選んだ数字は配列 perm に push() で追加します。あとは perm に格納されていない数字を選んでいくだけです。数字を 4 つ選んだら print() で perm を出力します。
そして、次の順列を発生させるため perm から pop() で数字を削除して、一つ前のループに後戻りします。選ぶ数字がなくなったならば、もう一つ前のループに後戻りします。このように、後戻りしながら数字を選んでいくことで、24 通りの順列を生成することができます。
このプログラムは 4 重のループですが、けっこうたいへんです。もし、1 から 10 の順列を発生させるとなると、10 重のループになってしまいます。ところが、再帰定義を使うともっと簡単にプログラムすることができます。リスト 8 を見てください。
リスト 8 : 順列の生成 (再帰版)
def make_perm(n, m = 0, perm = [])
if n == m
print perm, "\n"
else
for x in 1 .. n
next if perm.member? x
perm.push x
make_perm(n, m + 1, perm)
perm.pop
end
end
end
関数 make_perm(n) は、1 から n までの順列を生成します。考え方は繰り返し版と同じで、数字を選んで配列 perm に追加します。あとは perm にはない数字を選んでいきます。最初の呼び出しで 1 つの数字を選び、次の再帰呼び出しで 2 つめの数字を選びます。このように、n 重のループが n 回の再帰呼び出しに対応するわけです。
引数 m は選んだ数字の個数をカウントします。n と m が等しい場合は n 個の数字を選んだので perm を出力します。ここで n 番目の再帰呼び出しが終了し、n - 1 番目の再帰呼び出しに戻ります。そのあとは、pop() で選んだ数字を削除して新しい数字を選びます。もしも選ぶ数字がなければ、n - 2 番目の再帰呼び出しに戻り、n - 2 番目の数字を選び直します。これで 1 から n までの順列をすべて生成することができます。
それでは実行してみましょう。
irb> make_perm 4 [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] => 1..4
このように 24 通りの順列をすべて求めることができます。
●順列を配列に格納する
生成した順列を配列に格納して返す場合は、累積変数を使うと簡単です。プログラムはリスト 9 のようになります。
リスト 9 : 順列の生成 (2)
def make_perm1(n, m = 0, perm = [], a = [])
if n == m
a.push perm
else
for x in 1..n
if !perm.member? x
make_perm1(n, m + 1, perm + [x], a)
end
end
end
a
end
引数 a が累積変数で、ここに生成した順列をセットします。順列を一つ生成したら、引数 a に perm を追加します。make_perm1() を再帰呼び出しする場合、演算子 + で perm に [x] を追加して順列を生成します。このとき、新しい配列が生成されることに注意してください。このため、perm に追加した数値 x を取り除く必要はありません。最後に a を返します。
それでは実行してみましょう。
irb> make_perm1 4 [[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]]
このように、順列をリストに格納して返すこともできます。
●コラム たらいまわし関数
再帰を使った面白い関数を紹介しましょう。次のリストを見てください。
リスト : たらいまわし関数 def tarai(x, y, z) return y if x <= y tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)) end def tak(x, y, z) return z if x <= y tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y)) end
tarai() や tak() は「たらいまわし関数」といって、再帰的に定義されている関数です。これらの関数は Lisp などでベンチマークとして利用されることがあります。オリジナルの Lisp プログラムは Web サイト ぬえ 鵺 NUE の TAK Function をお読みください。
tarai() は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、tak() は tarai() のバリエーションで、John Macarthy 先生によって作成されたそうです。たらいまわし関数がベンチマークで使われていることは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。
Ruby の場合、たらいまわし関数は大変苦手だったのですが、YARV (Yet Another Ruby VM) を搭載したバージョン 1.9 以降は高速に実行できるようになりました。スクリプト言語の中では速いほうだと思います。
たらいまわし関数のような再帰関数は、一度計算した値を覚えておいて、同じ計算を何度も繰り返さないように工夫すると高速に実行することができます。このような手法を「表計算法」とか「メモ化」といいます。また、tarai() は「遅延評価」を行うと高速に実行することができます。ただし、tak() は遅延評価で高速化することはできません。
●おわりに
再帰定義について簡単に説明しました。はじめのうちは難しく感じるかもしれませんが、簡単なプログラムをいくつか作ってみてください。そのうちに、再帰定義に慣れてくると思います。たとえば、簡単なところでは累乗の計算とか組み合わせの生成、またはバックトラック法でパズルを解いてみるのも面白いと思います。
次回は Ruby の特徴であるイテレータとブロックを取り上げます。そして、その応用例として高階関数について説明します。