プログラミング言語SML#解説 3.7.1版
7 MLプログラミング入門

7.7 再帰的な関数

前節で学んだfun構文は再帰的な定義を許します. すなわち,この構文で定義される関数funNameを,関数定義本体 exprの中で使用することができます. このような再帰的な関数定義は,以下のような手順で設計していけば, 通常の算術関数と同じように自然に定義できるようになります.

  1. 1.

    関数funNameの振る舞いをあらかじめ想定する.

  2. 2.

    想定された振る舞いをする関数funNameがあると仮定し, 受け取った引数がparamの場合に返すべきか値を表す式expr を定義する.

例えば,第7.2節で紹介した階乗を計算す る関数factは以下のように設計できます.

  1. 1.

    factを階乗を計算する関数と想定します.

  2. 2.

    階乗を計算する関数factを使い,階乗の定義に従い,返すべき値を 以下のように定義する.

    1. (a)

      引数が0の場合,0の階乗は1であるから,1を返す.

    2. (b)

      0以外の一般の引数nの場合,階乗の定義から, n * fact (n - 1)を返す.

この2つの場合を単に書き下せば,以下の定義が得られます.

# fun fact 0 = 1
>   | fact n = n * fact (n - 1);
val fact = fn : int -> int

以上の考え方に従い種々の再起関数を簡単に定義できます. たとえば,すべての数の和を求める関数sumや引数nに対して与 えられた定数cn乗を計算するpowerなども,これら関数がすでにあ ると思うことによって,以下のように簡単に定義できます.

fun sum 0 = 0
  | sum n = n + sum (n - 1)
fun power 0 = 1
  | power n = c * power (n - 1)

sumpowerが想定した振る舞いをすると仮定すれば, 関数が返す値は正しいので,関数全体の定義も正しいことがわかります.