Ocaml一人勉強会 - 再帰関数と末尾再帰

関数型といえば再帰略。まあ例としてはつまらないんですが階乗計算を。

# let f n = if n > 0 then n * f (n-1) else 1;;
Characters 28-29:
  let f n = if n > 0 then n * f (n-1) else 1
                                 ^
Unbound value f

叱られてしまいました。そのままではそれまでに定義されていた f を参照してしまうのです（そして f は未定義なのでエラー）。
再帰関数を書くためには rec という予約語を指定してやる必要があります。recursive です。綴り怪しい。

# let rec f n = if n > 0 then n * f (n-1) else 1;;
val f : int -> int = <fun>
# f 10;;
- : int = 3628800

今度はちゃんと自分自身を参照しています。まあ普通。if 文が非常に気に食わないんですが、どうやら特に他に方法はないみたいです。あったら教えて下さい…
で再帰関数の中には末尾再帰と呼ばれる類の物が存在します。上のコードを末尾再帰で書きなおすと下のようになります。

# let f n =
  let rec iter x y = if x > 0 then iter (x - 1) (y * x) else y
  in iter n 1;;
val f : int -> int = <fun>
# f 3;;
- : int = 6

簡単にいうとその関数の返す値が、次に呼び出した関数の返す値になる再帰関数のことを指します。
これの何が嬉しいかというと関数呼び出しが最適化されるという。例えば末尾再帰ではない f にある程度大きな値を渡すと、

# f 100000;;
Stack overflow during evaluation (looping recursion?).

スタック飛んじゃいました。悲しいことです。そのくらい最適化してくれよと思ったらダメです。中の人も大変なんです。
一方末尾再帰では飛びません。値があんまり大きくなってしまうのでオーバーフローしすぎて0とかになってますが。

# f 100000;;
- : int = 0

まあOCamlにも普通に for や while のループはあるんですが別にいらないので省略。
まとめ：末尾再帰はえらいぞ！