さて、またまた問題です。次の式の値を求めてください。
1.
1
2.
1
* 2
3.
1
* 2 * 3
4.
1
* 2 * 3 * 4
5.
1
* 2 * 3 * 4 * 5
6.
1
* 2 * 3 * 4 * 5 * 6
これも計算自体は簡単ですが、やはり同じような式の繰り返しで、手動で入力するのは無駄な印象です。
そこで、正の整数nを受け取って、1からnまでの整数を掛けた値を返す関数factorialを考えてみます。まず、もしnが1だったら、factorial
1は「1から1までの整数を掛けた値」なので、明らかに1を返します。では、もしnが1より大きかったらどうでしょうか。さっきの問題を見ればすぐにわかると思いますが、n > 1のときは、一つ前のfactorial (n - 1)にnを掛けると、factorial
nが求まります。
以上のような関数を、OCamlでは次のように書くことができます。
# let rec factorial n =
if
n = 1 then 1 else
factorial (n - 1) * n ;;
val factorial : int -> int = <fun>
# factorial 1 ;;
- : int = 1
# factorial 2 ;;
- : int = 2
# factorial 3 ;;
- : int = 6
# factorial 10 ;;
- : int = 3628800
factorialは型int -> intすなわち整数を受け取って整数を返す関数ですが、定義の中でfactorial自身を呼び出しています。このように自分自身を用いて定義された関数を再帰関数と呼びます。OCamlでは、再帰関数を定義するときは、letの後にrecというキーワードを入れることになっています。2行目のif ... then ... else ...は、ifの後が真であればthenの部分が評価され、偽であればelseの部分が評価される、という式です。
余談ですが、このようにCやPerlなどの命令型言語ではループを利用するような場合でも、OCamlやHaskellのような関数型言語では再帰を利用するほうが普通です。変数の中身が後から変わる破壊的代入が不要となり、プログラムの見通しが良くなってバグが減ると考えられているからです。いまだにFortran言語など1960年代以来の伝統で「再帰はループより非効率的」という人もいますが、現代のコンピュータで問題になるほどの違いはありませんし、「末尾再帰」という処理によりループとまったく同様にコンパイルできることも少なくありません。
問題: 次の再帰関数は何を計算するか、当ててください。
1.
let
rec sum n =
if n = 0 then 0 else
sum (n - 1) + n
2.
let
rec gcd m n =
if m = 0 then n else
if m > n then gcd (m mod n) n
else
gcd (n mod m) m
3.
let
rec power m n =
if n = 0 then 1 else
if n mod 2 = 0 then power (m * m)
(n / 2) else
m * power m (n - 1)
解答:
1. 1からnまでの整数の総和
2. 非負整数mとnの最大公約数
3. mのn乗
2.は「mとnの最大公約数 = (m mod n)とnの最大公約数」という性質を利用したアルゴリズム、3.はm2n = (m2)n という性質を利用したアルゴリズムです。どちらも巧妙なアルゴリズムですが、ループで再帰よりわかりやすく書くのは難しいでしょう。