32.12 繰り返し

計算機の大きな特徴は，同じまたは似たような処理の繰り返しが高速にできることです．1つの例として，1から100までの和，つまり“1+2+…+99+100”を求めてみましょう．もちろん公式を使って“(1 + 100) * 100 / 2”とするのではなく，純粋に足し算を繰り返し行うのです．
繰り返し処理を行うとき，多くのプログラム言語では“for”や“while”や“loop”といったキーワードを利用することになります．OCamlでも“for”と“while”が用意されているのですが，あまり推奨されません．OCamlはプログラムの一部を切り取っても式になっていて値を持つという特徴がありますが，繰り返しを表す部分はこの枠組みから外れてしまうためです．
それではどうやって繰り返しをすればよいかというと，再帰関数を利用することになります．

再帰関数による繰り返し

今回の“1から100までの和”ですが，これは“1から99までの和”に“100”を足したものになっています．さらに“1から99までの和”というのは，“1から98までの和”に“99”を足したものです．
つまり，この和を求める計算は次のように考えることができます．

• “1から100までの和”は“1から99までの和”と“100”を足したもの．
• “1から99までの和”は“1から98までの和”と“99”を足したもの．
• “1から98までの和”は“1から97までの和”と“98”を足したもの．
• …
• “1から2までの和”は“1から1までの和”と“2”を足したもの．
• “1から1までの和”は…“1”に決まっている！

よく見ると，最後を除けば同じ形をしていますね．ですから，この考え方は次のように書くこともできます．

• “1からnまでの和”は“1から(n-1)までの和”と“n”を足したもの．
• “1から1までの和”は…“1”に決まっている！

ですから，“1から100までの和”を計算するというよりは，“1からnまでの和”を計算する関数“sum”を定義して“sum(100)”を計算することになります．
そして，“sum(n)”の計算には“sum(n – 1)”を使っているので，まさしく再帰関数なのです．つまり，

let rec sum(n) =
if n = 1 then 1 else sum(n - 1) + n;;

とすればよいはずです（ただしこの関数は引数に0以下の数を使うと止まらなくなるので注意してください）．

繰り返しの利用

では，再帰関数を使った繰り返しを試してみましょう．

let rec sum(n) = if n = 1 then 1 else sum(n - 1) + n;;

val sum : int -> int = <fun>

sum(10);;

- : int = 55

sum(100);;

- : int = 5050

(1 + 100) * 100 / 2;;

- : int = 5050