17.4.21 整数の和

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

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

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

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

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

# let rec sum(n) = return2 if n=0 then 0 return2 else (sum(n-1))+n;; return2 val sum : int -> int = <fun> #

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

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

# sum(10) ;; return2 - : int = 55 # 0+1+2+3+4+5+6+7+8+9+10;; return2 - : int = 55 # sum(4567) ;; return2 - : int = 10431028 # 4567*4568/2;; return2 - : int = 10431028 #