また再帰

自然数の構造に従った再帰

自然数:0から始まり、1,2,3と増え、無限に続く数。
自然数の様な無限に続くデータ構造を扱う場合には、まず、曖昧性の無い形で定義することが重要になる。

• 0は、自然数である。
• nが自然数ならn+1も自然数である。

階乗を求める再帰関数

自然数nの階乗n!は

n! = n * (n - 1) * .... * 1

で与えられる。

(* 自然数nの階乗を求める *)
(* fac : int -> int *)
let rec fac n = if n = 0 then 1
                else n * fac (n - 1)

(* テスト *)
let test1 = fac 0 = 1 
let test2 = fac 1 = 1 
let test3 = fac 2 = 2 
let test4 = fac 3 = 6 
let test5 = fac 4 = 24
let test6 = fac 10 = 3628800

自然数を扱う再帰の場合は、テンプレートは以下の様になる。

if n = 0 then (* nが0のケース *)
         else (* nが1以上のケース *) (* n-1が再帰のケース *)

ベキ乗を求める関数

(* 自然数m,nを受けとったらmのn乗を求める *)
(* power : int -> int -> int *)
let rec power m n = if n = 0 then 1
                    else m * power m (n - 1)

(* テスト *)
let test1 = power 3 0 = 1 
let test2 = power 3 1 = 3 
let test3 = power 3 2 = 9 
let test4 = power 3 3 = 27