繰り返しと末尾再帰 (2/2)


再帰で繰り返しを真似てみよう: 末尾再帰

では、Scheme で再帰をもちいて、 C の繰り返しを用いた階乗のプログラムを真似てみたらどうなるでしょうか? 実は、下の様に書くことが出来ます。
(define (fact2-iter i n result)
    (if (<= i n)
        (fact2-iter (+ i 1) n (* result i))
        result))

(define (fact2 n)
    (fact2-iter 1 n 1))
C では、繰り返し文一回あたり、 i, result の更新(つまりは代入)を繰り返していました。 でも、関数型プログラミングに代入はそぐいません。

関数型プログラミングにおいて繰り返しを真似るためには、 繰り返し 1 回分を fact2-iter の様な関数として表すことになります。 では、もともとの C のプログラム では繰り返し 1 回分では何が行われていたのでしょう? i, n, result という値を受け取っていて、 まず繰り返しの終了判定を行い、 引続き行う場合は i, n, result を新たな値に更新し、自分自身を繰り返していました。 上述の関数は、繰り返し 1 回分を忠実に関数に作り変えたものです(不等号が逆だが)。

C の関数の初期値設定ならびに返り値を返す部分は、 それぞれ fact2fact2-iter の繰り返し終了時の式として現われています。

この program でもちいられている再帰は、始めの program の場合と異なり、 再帰が深く呼ばれる必要はありません。 なぜなら、再帰の結果を待って何かを行うのではないからです。 このような、再帰的な関数呼び出しが帰り値の表現の中でのみおこなわれるものを、 末尾再帰 (tail call recursion) と呼びます。

ものは試して、 (fact2 5)STEP 機能 にかけてみて下さい。違いが良く分かると思います。

末尾再帰は、一般の再帰に比べてより効率的に実行させることが 可能です。 これは、関数型に限らず C 言語などにおいても同様です。

その他

関連情報は、こちら

末尾再帰について良く分からなかった人は、 別に無理してプログラミングに使わなくても良いです。


99.9.29/ Tomio KAMADA: kamada@cs.kobe-u.ac.jp