再帰関数

文法は「let rec fname p0 p1 p2 ... = expr」です。
とりあえず、再帰といえばn!とかΣnの計算らしいです。どう考えても再帰の例として正しくない気はしますが。

# let rec f x = if x > 1 then x + f x - 1 else 1;;
val f : int -> int = <fun>
<||
なんだか懐かしい感じの文字列が見えます。手続き脳のトモダチ、if then elseです。
OCamlにおけるif文は最後に評価した値を返します。if文というか、if式ですね。
さて呼び出してみます。
>||
# f 5;;
Stack overflow during evaluation (looping recursion?).

おっと、叱られてしまいました。
これは「f (x - 1)」のつもりが「(f x) - 1」と解釈されているせいですね。
ちゃんと括弧はさぼらず書きましょう！

# let rec f x = if x > 1 then x + f (x - 1) else 1;;
val f : int -> int = <fun>
# f 5;;
- : int = 15

しかしこれ、正しく記述していても、fに渡す整数が大きかったら当たり前ですがスタック飛びそうですね。

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

飛びました。ちなみにもうちょっと小さい数字だと、ちゃんと（？）オーバーフローもします。
さて、こういう時は末端再帰を使うらしいです。末端再帰だと、コンパイラがループに直してくれるようです。
上のコードを末端再帰で書き直すと大体こうなります。

# let f x = let rec g x y = if x > 0 then g (x - 1) (x + y) else y in g x 0;;
val f : int -> int = <fun>
# f 5;;
- : int = 15

今度は見慣れない文字列が。inを使うとローカル変数を作る事が出来るようです。
この場合、関数fに対してローカルな再帰関数gを定義した上で「let f x = g x 0」が呼ばれるわけです。
「let f x = g x 0 local let g x y = ...」みたいな感じで、定義後ろに持ってこれないかな…と思うんですが、そういう文法あるのかなあ。ないだろうなあ。