再帰定義
関数を定義するとき、その関数自身を呼び出すことを「再帰呼び出し (recursive call)」とか「再帰定義 (recursive definition)」といいます。関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。ところが、再帰定義は特別なことではありません。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。
ところが、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックの一つと思い込んでしまい、初心者の方は避けて通ることが多いように思います。再帰定義は、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。とくに関数型言語の場合、再帰定義を積極的に活用してプログラミングを行うので、初心者の方が覚えるべき基礎テクニックのひとつにすぎません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。
●再帰定義の基本
まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を図 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 を見てください。
図 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 の y 乗という x を y 回掛ける計算です。累乗は x の右上に小さく y を書くことで表されますが、ここでは x ** y と書くことにします。
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 は次のように定義することができます。
図 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) の値を求めておくことで、累乗を効率的に計算することができます。
●フィボナッチ関数
もうひとつ簡単な数値計算の例を示しましょう。フィボナッチ関数も再帰的に定義される関数です。
\( fibo(n) = \begin{cases} 0 & if \ n = 0 \\ 1 & if \ n = 1 \\ fibo(n - 1) + fibo(n - 2) & if \ n \gt 1 \end{cases} \)
0, 1, 1, 2, 3, 5, 8, 13 .... という直前の 2 項を足していく数列
図 6 : フィボナッチ関数の定義
フィボナッチ関数も再帰定義を使えば簡単にプログラムできます。
リスト 5 : フィボナッチ関数 let rec fibonacci n = if n < 2 then n else fibonacci (n - 1) + fibonacci (n - 2)
関数 fibonacci は fact とは違い、自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibonacci の呼び出しをトレースすると下図のようになります。
# #trace fibonacci;; fibonacci is now traced. # fibonacci 5;; fibonacci <-- 5 fibonacci <-- 3 fibonacci <-- 1 fibonacci --> 1 fibonacci <-- 2 fibonacci <-- 0 fibonacci --> 0 fibonacci <-- 1 fibonacci --> 1 fibonacci --> 1 fibonacci --> 2 fibonacci <-- 4 fibonacci <-- 2 fibonacci <-- 0 fibonacci --> 0 fibonacci <-- 1 fibonacci --> 1 fibonacci --> 1 fibonacci <-- 3 fibonacci <-- 1 fibonacci --> 1 fibonacci <-- 2 fibonacci <-- 0 fibonacci --> 0 fibonacci <-- 1 fibonacci --> 1 fibonacci --> 1 fibonacci --> 2 fibonacci --> 3 fibonacci --> 5 - : int = 5
図 7 : fibonacci のトレース
同じ値を何回も求めているため、効率はとても悪いのです。もちろん、高速に求める方法があるので、心配しないで下さい。
●ユークリッドの互除法
フィボナッチ関数は二重再帰でプログラムしたので実行速度はとても遅いのですが、再帰定義を使うと非効率的なプログラムになるというわけではありません。累乗のプログラムのように、再帰定義でも効率的なプログラムを作ることができます。たとえば、負でない整数 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 が最大公約数になります。
プログラムは再帰定義を使って簡単に作ることができます。リスト 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 \mathrm{C}_r\) と表記します。\({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。
皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。M.Hiroi が使用している OCaml の整数 (int) は最大で 4611686018427387903 までなので、この公式をそのままプログラムするわけにはいきません。そこで、次の公式を使うことにします。
この式は \({}_n \mathrm{C}_r\) と \({}_n \mathrm{C}_{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 (54, 27);; - : int = 1946939425648112 # comb (56, 28);; - : int = 7648690600760440 # comb (58, 29);; - : int = 30067266499541040 # comb (60, 30);; - : int = 118264581564861424 # comb (62, 31);; - : int = -147959044004670535
comb (62, 31) で桁あふれが発生して、結果は負の値になりました。このプログラムを実際に使う場合は、桁あふれに十分注意してください。
●ハノイの塔
再帰といえば忘れてはいけないのが「ハノイの塔」でしょう。ハノイの塔は棒に刺さっている円盤を、次に示す規則に従ってほかの棒にすべて移動させる問題です。
- 1 回に 1 枚の円盤しか動かせない。
- 小さな円盤の上に大きな円盤を乗せることはできない。
- 最初は 1 本の棒に、大きい円盤の上に小さな円盤が順番に刺さっている。
ハノイの塔は、再帰を使えば簡単に解ける問題です。たとえば、5 番目の円盤を左から中央の棒に移す場合、その上の 4 枚の円盤を右の棒に移しておけば、5 番目の円盤を動かすことができるようになります。そして、5 番目の円盤を中央に移したら、右の棒に移した 4 枚の円盤を中央の棒に移すことを考えればよいわけです。したがって、n 枚の円盤を左から中央の棒に移すプログラムは次のように表現できます。
- n - 1 枚の円盤を左から右に移す
- n 枚目の円盤を左から中央へ移す
- n - 1 枚の円盤を右から中央へ移す
これを素直にプログラムすると次のようになります。
リスト 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 で表示します。
●unit 型と逐次実行
print_string は文字列を画面へ表示する関数です。次の例を見てください。
# print_string "hello, world\n";; hello, world - : unit = ()
print_string は画面に文字列を出力する「副作用 (side effect)」が目的の関数です。hello, world は出力結果であり、print_string の返り値ではありません。() が print_string の返り値で、これを「ユニット (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 = ()
●問題
次の関数を再帰を使って定義してください。
- hello, world を n 回表示する関数 print_hello n
- 文字列 OCaml を n 行 m 列に表示する関数 print_ocaml n m
- 整数 1 から n までの総和を求める関数 sum n
- 整数 1 から n までの平方数の総和を求める関数 square_sum n
- 整数 1 から n までの三乗数の総和を求める関数 cube_sum n
●解答
# let rec print_hello n = if n = 0 then () else begin print_string "hello, world\n"; print_hello (n - 1) end;; val print_hello : int -> unit = <fun> # print_hello 10;; hello, world hello, world hello, world hello, world hello, world hello, world hello, world hello, world hello, world hello, world - : unit = () # let rec print_ocaml_line m = if m = 0 then print_newline() else begin print_string "OCaml "; print_ocaml_line (m - 1) end;; val print_ocaml_line : int -> unit = <fun> # print_ocaml_line 5;; OCaml OCaml OCaml OCaml OCaml - : unit = () # let rec print_ocaml (n, m) = if n = 0 then print_newline() else begin print_ocaml_line m; print_ocaml (n - 1, m) end;; val print_ocaml : int * int -> unit = <fun> # print_ocaml (3, 4);; OCaml OCaml OCaml OCaml OCaml OCaml OCaml OCaml OCaml OCaml OCaml OCaml - : unit = () # let rec sum n = if n = 0 then 0 else n + sum (n - 1);; val sum : int -> int = <fun> # sum 10;; - : int = 55 # sum 1000;; - : int = 500500 # let rec square_sum n = if n = 0 then 0 else square n + square_sum (n - 1);; val square_sum : int -> int = <fun> # square_sum 10;; - : int = 385 # square_sum 1000;; - : int = 333833500 # let cube x = x * x * x;; val cube : int -> int = <fun> # let rec cube_sum n = if n = 0 then 0 else cube n + cube_sum (n - 1);; val cube_sum : int -> int = <fun> # cube_sum 10;; - : int = 3025 # cube_sum 100;; - : int = 25502500
改訂 2020 年 6 月 21 日