関数を定義するとき、その関数自身を呼び出すことを「再帰呼び出し (recursive call) 」とか「再帰定義 (recursive definition) 」といいます。関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。ところが、再帰定義は特別なことではありません。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。
ところが、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックの一つと思い込んでしまい、初心者の方は避けて通ることが多いように思います。再帰定義は、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。とくに関数型言語の場合、再帰定義を積極的に活用してプログラミングを行うので、初心者の方が覚えるべき基礎テクニックのひとつにすぎません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。
まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を図 1 に示します。
0! = 1 n! = n * (n - 1)! 図 1 : 階乗の定義
階乗の定義からわかるように、n の階乗は n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。リスト 1 を見てください。
リスト 1 : 階乗 let rec fact n = if n = 0 then 1 else n * fact (n - 1)
関数 fact は引数 n が 0 であれば 1 を返し、そうでなければ n * fact (n - 1) の計算結果を返します。fact の定義で fact 自身を呼び出しています。これが再帰呼び出しです。Ocaml の場合、関数を再帰呼び出しする場合は let の後ろに rec をつけます。rec がないとエラーになります。ご注意ください。
それでは、本当にこれで階乗を計算できるのか、実際に試してみましょう。OCaml には「トレース」という関数の実行を追跡する機能が用意されています。ディレクティブ #trace でトレースする関数名を指定します。トレースを解除する場合はディレクティブ #untrace を使います。fact 4 をトレースすると、次のようになります。
# #trace fact;; fact is now traced. # fact 4;; fact <-- 4 fact <-- 3 fact <-- 2 fact <-- 1 fact <-- 0 fact --> 1 fact --> 1 fact --> 2 fact --> 6 fact --> 24 - : int = 24
確かに階乗の答えを求めることができました。
それでは、再帰定義のポイントを説明しましょう。図 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 回目の呼び出し (Call:2) では、引数 n は 3 に束縛されます。ここで、最初に呼び出したときと、2 回目に呼び出したときでは、引数 n の値が違うことに注意してください。
関数の引数は局所変数として扱われます。前回説明したように、局所変数には有効範囲（スコープ）があります。引数の場合、その関数が実行されている間だけ有効です。関数呼び出しが行われるたびに新しい局所変数を生成して、そこに値を束縛します。そして、関数の実行が終了すると、生成された局所変数は廃棄されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 n は名前が同じでも異なる変数になるのです。ここが再帰呼び出しを理解するポイントの一つです。
プログラムを見ると変数 n は一つしかありませんが、再帰呼び出しが行われるたびに新しい変数 n が作られていくと考えてください。fact 4 を実行しているときの n は 4 であり、fact 3 を呼び出すときには、この n の値を書き換えるのではなく、新しい変数 n を用意して、そこに 3 を束縛するのです。
同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 n が 0 になります。このとき、if の then 節が実行され 1 が返されます。ここで再帰呼び出しが止まります。これを再帰呼び出しの停止条件といいます。ここが第 2 のポイントです。
停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、OCaml であればプログラムの実行は途中で停止します。再帰呼び出しを使う場合は、この停止条件に十分注意してください。
fact 0 は 1 を返して fact 1 に戻ります。fact 1 を実行しているあいだ、引数 n の値は 1 です。したがって、fact 1 の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact 4 の値 24 を求めることができます。
それでは簡単な例題として累乗を求める関数 pow を作ってみましょう。累乗は x の n 乗という x を n 回掛ける計算です。累乗は x の右上に小さく n を書くことで表されますが、ここでは 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; 図 3 : 累乗の計算
今回のプログラムは、引数 x を実数、y を整数とします。そうすると、x ** y は次のように定義することができます。
x ** 0 = 1
x ** y = x * (x ** (y - 1))
図 4 : 累乗の定義
階乗の場合と同様に、x ** y は x ** (y - 1) がわかれば求めることができます。プログラムは次のようになります。
リスト 2 : 累乗 (1) let rec pow (x, y) = if y = 0 then 1.0 else x *. pow (x, y - 1)
再帰定義を使って x ** y を計算しています。手続き型言語では単純な繰り返しで実現できる処理ですが、関数型言語では単純な繰り返しでも再帰定義を使って実現します。
関数 pow は 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 は奇数）
図 5 : 累乗の高速化
階乗の計算では n を n - 1 の計算に置き換えていきますが、累乗の場合は y を y / 2 に置き換えていくことができます。y が半分になっていくので減少の度合いが大きくなり、計算回数は少なくて済みます。これを単純にプログラムすると、次のようになります。
リスト 3 : 累乗 (2) let rec pow (x, y) = if y = 0 then 1.0 else if y mod 2 = 0 then pow (x, y / 2) *. pow (x, y / 2) else x *. pow (x, y / 2) *. pow (x, y / 2)
y が偶数の場合でも奇数の場合でも、pow (x, y / 2) を 2 回呼び出していますね。同じ計算を 2 回しているのは無駄なので、let を使って局所変数を定義します。次のリストを見てください。
リスト 4 : 累乗 (3)
let rec pow (x, y) =
if y = 0 then 1.0
else
let z = pow (x, y / 2) in
let zz = z *. z in
if y mod 2 = 0 then zz else x *. zz
let で局所変数 z と zz を定義します。z の値は x ** (y/2) です。これは pow を再帰呼び出しすれば簡単に求めることができます。zz の値は z ** 2 になります。あとは、y が偶数であれば、zz をそのまま返し、奇数であれば x *. zz を返します。このように、局所変数 z に pow (x, y / 2) の値を求めておくことで、累乗を効率的に計算することができます。
もうひとつ簡単な数値計算の例を示しましょう。フィボナッチ関数も再帰的に定義される関数です。
┌ 1 : n = 0
f(n) = ┤ 1 : n = 1
└ f(n-1) + f(n-2) : n > 1
1, 1, 2, 3, 5, 8, 13 .... という直前の 2 項を足していく数列
図 6 : フィボナッチ関数の定義
フィボナッチ関数も再帰定義を使えば簡単にプログラムできます。
リスト 5 : フィボナッチ関数 let rec fibonacci n = if n = 0 || n = 1 then 1 else fibonacci (n - 1) + fibonacci (n - 2)
関数 fibonacci は fact とは違い、自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibonacci の呼び出しをトレースすると下図のようになります。
f(5) ┬ f(4) ┬ f(3) ┬ f(2) ┬ f(1)
│ │ │ │
│ │ │ └ f(0)
│ │ └ f(1)
│ └ f(2) ┬ f(1)
│ │
│ └ f(0)
│
└ f(3) ┬ f(2) ┬ f(1)
│ │
│ └ f(0)
└ f(1)
図 7 : fibonacci のトレース
同じ値を何回も求めているため、効率はとても悪いのです。もちろん、高速に求める方法があるので、心配しないで下さい。
フィボナッチ関数は二重再帰でプログラムしたので実行速度はとても遅いのですが、再帰定義を使うと非効率的なプログラムになるというわけではありません。累乗のプログラムのように、再帰定義でも効率的なプログラムを作ることができます。たとえば、負でない整数 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 が最大公約数になります。
プログラムは再帰定義を使って簡単に作ることができます。リスト 6 を見てください。
リスト 6 : 最大公約数 let rec gcd (a, b) = if b = 0 then a else gcd (b, a mod b)
関数 gcd は引数 a と b の最大公約数を求めます。b が 0 の場合は a を返します。これが再帰呼び出しの停止条件になります。そうでなければ gcd を再帰呼び出しして、b と a mod b の最大公約数を求めます。リスト 6 はユークリッドの互除法の定義をそのままプログラムしただけです。このように、再帰定義を使うと簡単にプログラムを作ることができます。
それでは実行例を示しましょう。
# gcd (42, 30);; - : int = 6 # gcd (15, 70);; - : int = 5
最小公倍数は最大公約数を使って簡単に求めることができます。リスト 7 を見てください。
リスト 7 : 最大公倍数 let lcm (a, b) = a * b / gcd (a, b)
整数 a と b の最小公倍数は a * b / gcd(a, b) で求めることができます。実行例を示します。
# lcm(5, 7);; - : int = 35 # lcm(14, 35);; - : int = 70
次は組み合わせの数を求めるプログラムを作ってみましょう。ここでは組み合わせの数を nＣr と表記します。nＣr を求めるには、次の公式を使えば簡単です。
nＣr = n * (n - 1) * (n - 2) * ... * (n - r + 1) / (1 * 2 * 3 * ... * r)
皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。OCaml の整数 (int) は最大で 1073741823 までなので、この公式をそのままプログラムするわけにはいきません。そこで、次の公式を使うことにします。
nC0 = nCn = 1 nCr = nCr-1 * (n - r + 1) / r
この式は nＣr と nＣr-1 の関係を表しています。あとは階乗と同じように、再帰定義を使って簡単にプログラムできます。次のリストを見てください。
リスト 8 : 組み合わせの数を求める let rec comb (n, r) = if n = r || r = 0 then 1 else comb (n, r - 1) * (n - r + 1) / r
とても簡単ですね。しかしながら、このプログラムでも桁あふれする場合があります。どこまで計算できるか試してみましょう。
# comb (16, 8);; - : int = 12870 # comb (18, 9);; - : int = 48620 # comb (20, 10);; - : int = 184756 # comb (22, 11);; - : int = 705432 # comb (24, 12);; - : int = 2704156 # comb (26, 13);; - : int = 10400600 # comb (28, 14);; - : int = 40116600 # comb (30, 15);; - : int -58844218
comb (30, 15) では桁あふれが発生して、結果は負の値になりました。このプログラムを実際に使う場合は、桁あふれに十分注意してください。
再帰といえば忘れてはいけないのが「ハノイの塔」でしょう。ハノイの塔は棒に刺さっている円盤を、次に示す規則に従ってほかの棒にすべて移動させる問題です。
ハノイの塔は、再帰を使えば簡単に解ける問題です。たとえば、5 番目の円盤を左から中央の棒に移す場合、その上の 4 枚の円盤を右の棒に移しておけば、5 番目の円盤を動かすことができるようになります。そして、5 番目の円盤を中央に移したら、右の棒に移した 4 枚の円盤を中央の棒に移すことを考えればよいわけです。したがって、n 枚の円盤を左から中央の棒に移すプログラムは次のように表現できます。
これを素直にプログラムすると次のようになります。
リスト 9 : ハノイの塔
let print_hanoi (from, to_) =
print_string ("fromt " ^ from ^ " to " ^ to_ ^ "\n")
let rec hanoi (n, from, to_, via) =
if n = 1 then print_hanoi (from, to_)
else begin
hanoi (n - 1, from, via, to_);
print_hanoi (from, to_);
hanoi (n - 1, via, to_, from)
end
n は動かす円盤の枚数、from は移動元の棒、to_ は移動先の棒、via は残りの棒を示します。円盤の枚数が 1 枚の場合は簡単です。from にある円盤を to_ へ移すだけです。これが再帰の停止条件になります。移動手順を関数 print_hanoi で表示します。
print_string は文字列を画面へ表示する関数です。次の例を見てください。
# print_string "hello, world\n";; hello, world - : unit = ()
print_string は画面に文字列を出力する「副作用 (side effect) 」が目的の関数です。hello, world は出力結果であり、print_string の返り値ではありません。() が print の返り値で、これを「ユニット (unit) 」といいます。unit 型のデータは () しかなく、print_string のように副作用が目的の関数の返り値などで使用されます。
円盤が複数枚ある場合、from にある円盤の n - 1 枚を via に移します。この処理は hanoi を再帰呼び出しすればいいですね。次に、残りの 1 枚を to_ に移します。これを print_hanoi で表示します。そして、via に移した n - 1 枚の円盤を to_ に移します。この処理も hanoi を再帰呼び出しするだけです。
このように、式を順番に実行するとき、OCaml は式をセミコロン ( ; ) で区切ります。これを「逐次実行」といいます。逐次実行は最後に評価した式の値を返します。それ以外の式の結果は捨てられます。このため、返り値が unit 以外の場合、コンパイル時に警告がでるので注意してください。
簡単な例を示しましょう。
# let print_foo n = print_string "foo = "; print_int n; print_newline ();; val print_foo : int -> unit = <fun> # print_foo 10;; foo = 10 - : unit = ()
print_int は整数を表示する関数で、print_newline は改行を出力する関数です。print_newline の型を示します。
# print_newline;; - : unit -> unit = <fun>
引数のない関数を呼び出す場合、OCaml では unit を渡します。print_newline だけでは関数を呼び出すことはできません。また、逐次実行の範囲を明確にしたい場合は、複数の式を begin ... end またはカッコ ( ) で囲みます。hanoi の場合、else 節を begin ... end で囲まないと正常に動作しません。ご注意ください。
これでプログラムは完成です。それでは実行してみましょう。
# hanoi (3, "A", "B", "C");; from A to B from A to C from B to C from A to B from C to A from C to B from A to B - : unit = ()
相互再帰とは、関数 foo が関数 bar を呼び出し、bar でも foo を呼び出すというように、お互いに再帰呼び出しを行っていることをいいます。OCaml はコンパイル時に型チェックを行うプログラミング言語なので、foo から bar を呼び出そうとしても、bar が未定義の場合はコンパイルでエラーになります。このため、OCaml では相互再帰を次のように定義します。
let rec f1 a1 = 式1 and f2 a2 = 式2 ... and fn an = 式n
相互再帰を行っている関数を and でつなげて定義します。OCaml の場合、and は論理演算子ではありません。論理演算子には && を使います。
それでは簡単な例を示しましょう。次のリストを見てください。
リスト 10 : 相互再帰 let rec foo n = if n = 0 then true else bar (n - 1) and bar n = if n = 0 then false else foo (n - 1)
このプログラムは関数 foo と bar が相互再帰しています。foo と bar が何をしているのか、実際に動かしてみましょう。
# bar 3;; - : bool = true # bar 2;; - : bool = false # bar 1;; - : bool = true # foo 3;; - : bool = false # foo 2;; - : bool = true # foo 1;; - : bool = false
結果を見ればおわかりのように、foo は n が偶数のときに真を返し、bar は n が奇数のときに真を返します。なお、このプログラムはあくまでも相互再帰の例題であり、実用的なプログラムではありません。
再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰 (tail recursion) 」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶことがあります。末尾再帰は簡単な処理で繰り返しに変換できることが知られています。
ML や Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰を繰り返しに変換する処理系があります。この機能を「末尾再帰最適化」[*1] といいます。なかには Scheme [*2] のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。
たとえば、階乗を計算する関数 fact を思い出してください。リスト 1 の fact は最後に n と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換するとリスト 11 になります。
リスト 11 : 階乗 (末尾再帰) let rec facti (n, a) = if n = 0 then a else facti (n - 1, a * n) let fact n = facti (n, 1)
関数 facti を見てください。最後の再帰呼び出しで、facti の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれません。そこが再帰呼び出しの面白いところです。このプログラムでは引数 a の使い方がポイントです。
たとえば facti 4 を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算します。このとき、計算の途中経過を引数 a に記憶しているのです。facti の呼び出しをトレースすると次のようになります。
# facti (4, 1);; facti <-- (4, 1) facti <-- (3, 4) facti <-- (2, 12) facti <-- (1, 24) facti <-- (0, 24) facti --> 24 facti --> 24 facti --> 24 facti --> 24 facti --> 24 - : int = 24
引数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。
純粋な関数型言語の場合、while や for などの繰り返しがないプログラミング言語 [*3] があります。また、論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を用いてプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。
ところで、関数 facti は fact からしか呼び出されていません。このような場合、facti は let で局所的な関数として定義するといいでしょう。プログラムは次のようになります。
リスト 12 : 階乗の計算 (末尾再帰)
let fact n =
let rec facti (n, a) =
if n = 0 then a else facti (n - 1, a * n)
in
facti (n, 1)
今度は累算変数を使って、二重再帰を末尾再帰へ変換してみましょう。例題としてフィボナッチ関数を取り上げます。リスト 5 のフィボナッチ関数は二重再帰になっているので、とても時間がかかります。二重再帰を末尾再帰に変換すると、プログラムを高速に実行することができます。リスト 13 を見てください。
リスト 13 : フィボナッチ関数(末尾再帰)
let fibonacci n =
let rec fibo (n, a1, a2) =
if n = 0 then a1 else fibo (n - 1, a1 + a2, a1)
in
fibo (n, 1, 0)
累算変数 a1 と a2 の使い方がポイントです。現在のフィボナッチ数を変数 a1 に、ひとつ前の値を変数 a2 に格納しておきます。あとは a1 と a2 を足し算して、新しいフィボナッチ数を計算すればいいわけです。fibo の呼び出しを図に示すと、次のようになります。
fibo (5, 1, 0)
fibo (4, 1, 1)
fibo (3, 2, 1)
fibo (2, 3, 2)
fibo (1, 5, 3)
fibo (0, 8, 5)
=> a1 の値 8 を返す
=> 8
=> 8
=> 8
=> 8
=> 8
図 8 : 関数 fibo の呼び出し
二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う処理系では、プログラムをより高速に実行できるでしょう。
末尾再帰 (繰り返し) は再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるのに、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムがいちばんです