MLの基礎（２） - FreeBSDな日々

text p.42-p.45

• 帰納的関数(recursive function)

たとえば、
sum = 1+2+3+....+n
を定義するとき、関数型言語ではよく次のパターンを使う。

fun sum n = n + sum(n-1)

つまり、sum = n + (1+2+...+(n-1))
このsum(n-1)を繰り返し、適用（評価することで）
sum = n + (n-1)+...+ 2 + 1
を得る。

例　sum 5 =>5 + sum(4) => 5+ 4 +sum(3) => 5+4+3+sum(2)
=> 5+4+3+2+sum(1) => 5+4+3+2+1

このように、関数の定義に自分自身が含まれる場合を
帰納的定義という。

ただ、先に定義は不完全な定義である。n-1が永遠に評価されるので、
繰り返しが止まることがない。
停止条件 (base case) は、n=0のとき、このとき、0を与えればよい。

かくして、次のように定義される。

fun sum n = if n = 0 then 0 else n + sum(n-1)

ここで、停止条件が最初に来ているのがみそである。
if文だからよいが、ケース分けの場合は必ず最初にくる必要がある。

また、ＭＬはパターンマッチングが強力であり、これを使うと、

fun sum 0 = 0 | sum n = n + sum(n-1)
と書ける。これは、
sum 0 は0と評価（置き換え）し、それ以外、sum n は　n+sum(n-1）と評価（置き換え）するという意味である。
この場合は、停止条件を先に書かないと永遠に繰り返されることが一目瞭然だろう。