Ch.7 MLプログラミング入門

§ 7.16. ループと末尾再帰関数

くり返し処理(ループ)の設計の基本は,

  1. 求める値に至る(それを特別な場合として含む)計算の途中状態を設計し、

  2. 計算(の途中)結果を保持するための変数と

  3. 計算の進行状態を保持する変数,

を用意し最終状態のチェックしながら,これら変数を更新するコードを書くこと です. 1からnまでの積を求める場合は,

  • 途中の計算状態: s=i*(i+1)**n

  • 計算結果を持つ変数:s

  • 計算の状態を保持する変数:i

と考え,最終状態(i=0)をチェックし変数を変更するコードを書くと 前のfactのようなコードとなります. この考え方に従えば,種々の複雑な処理をループとして書き下すことが できます.

この考え方は,手続き型言語に特有のものではありません. 手続き型言語では,計算結果を持つ変数と状態を制御する変数の値を変 更しながらループします. この変数の変更とループは,

変数の現在の値を受け取り,新しい値を生成する関数

と考えると,自分自身を呼び出すだけの関数となります. C言語のfact関数で表現されたループコードは,以下のMLコード で実現できます.

  fun loop (0, s) = s
    | loop (n, s) = loop (n - 1, s * n)
  fun fact n = loop (n, 1)

このloopが行う自分自身を呼び出すだけの再帰関数を末尾再帰と 呼びます. 末尾再帰は,手続き型言語のループと同様の実行列にコンパイルされ効 率よく実行されます.