第11章　自然数と再帰

11.1　自然数の構造

自然数は、以下のように定義できる。

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

自己参照しており、自然数もリストと同じように再帰的なデータ型であると言える。

そのため、自然数の構造に基づいた再帰関数を定義することが出来る。

11.2　自然数に基づいた再帰関数

自然数に基づいた再帰関数の例として、階乗（n!）を求める関数facを作っていく。

0の階乗は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

デザインレシピに従い、まずはヘッダを作る。

(* 目的：自然数 n の階乗を求める *)
(* fac: int -> int *)
let rec fac n = 0

次に、テンプレート。
リストのときと同様に、自己参照していないケースと、自己参照しているケースに分ける。
自然数における自己参照していないケースとはつまり、0のケースのこと。

let rec fac n = if n = 0
  then 0
  else 0 (* fac (n - 1) *)

あとは、本体部分を書けばよい。

let rec fac n = if n = 0
  then 1
  else n * fac (n - 1)

11.3　べき乗を求める関数

省略。

11.4　リスト上の再帰との違い

n - 1以外に対して再帰を行う場合は、停止性、つまり再帰が止まることについて、考慮しなければならない。
例えばn - 2に対して再帰呼び出しを行うと、nが偶数のときはやがて0のケースに帰着して再帰呼び出しは停止するが、奇数だった場合0のケースを通り過ぎてしまい、再帰呼び出しが無限に繰り返されてしまう。