17.4.21 整数の和

計算機の大きな特徴は，同じことを繰り返すことが高速にできることです．1つの例として，0 + 1 + ...+ 99 + 100 つまり0から100までの和を求めてみましょう．

この和を求める計算は次のように考えることができます．

• もし「0から99までの和」が x だとしたら，「0から100」までの和は x + 100 である．
• もし「0から98までの和」が y だとしたら，「0から99」までの和は y + 99 である．
• もし「0から97までの和」が z だとしたら，「0から99」までの和は z + 98 である．
• ...
• もし「0から0までの和」が a だとしたら，「0から1」までの和は a + 1 である．
• もし「0から0までの和」は0に決まっている!

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

• もし「0から(n-1)までの和」が x だとしたら，「0からn」までの和は x + n である．
• もし「0から0までの和」は0に決まっている!

この考え方は，「0からある数までの和」を「0から1つ小さい数までの和」を使って定義している点がポイントです．このような考え方は，Ocamlでは let rec 名前(変数,変数,..) = 式 という形で定義することができます．

「0からnまでの和」をsum(n)という関数として定義するのであれば，次のようになります．

定義の仕方は，いままでの関数の定義とほとんど同じですが，唯一，letの後にrecがあるのだけが違いです．

使い方もいままでの関数と同じです．0から10までの和や4567までの和を求めてみましょう． 因みに0からnまでの和は n×(n+1)÷2 だということが知られていますので，そうやって計算した場合と同じになることも確めておきましょう．