相互再帰とは、関数 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 の呼び出し
二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う処理系では、プログラムをより高速に実行できるでしょう。
末尾再帰 (繰り返し) は再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるのに、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムがいちばんです
次の再帰関数を末尾再帰に直してください。
# let rec sum (n, a) = if n = 0 then a else sum (n - 1, a + n);; val sum : int * int -> int = <fun> # sum (10, 0);; - : int = 55 # sum (1000, 0);; - : int = 500500 # let square x = x * x;; val square : int -> int = <fun> # let rec square_sum (n, a) = if n = 0 then a else square_sum (n - 1, a + square n);; val square_sum : int * int -> int = <fun> # square_sum (10, 0);; - : int = 385 # square_sum (1000, 0);; - : int = 333833500 # let cube x = x * x * x;; val cube : int -> int = <fun> # let rec cube_sum (n, a) = if n = 0 then a else cube_sum (n - 1, a + cube n);; val cube_sum : int * int -> int = <fun> # cube_sum (10, 0);; - : int = 3025 # cube_sum (100, 0);; - : int = 25502500