補足 (再帰関数)

繰り返し文

実は Scheme には繰り返しを表現する do 文などがあります( R5RS)。 でも、今回は Scheme の特徴である、tail call recursion の練習のため教えていません。

末尾再帰の高効率実装

既存アーキテクチャにおいて関数呼び出しを行う場合、 普通スタックというデータ構造を用います。 関数呼び出しからの復帰をおこなうために、 呼び出し側の状態(局所変数の状態やprogram counter など; フレームと呼ばれる) をスタックの上に保存しておき、 呼び出された側から復帰する際に、スタック上のデータをもちいて計算を復帰します。 再帰の深くなる program の場合、スタックがどんどん積まれていった後に、 順々にもどってくることになります。

一方、末尾再帰の場合、関数呼び出しから戻ってきてから行う操作は存在しません。 このため、関数呼び出しと自分自身の関数の戻り操作を同時に行ってしまうことが出来ます。 即ち、自分の実行にもちいていたフレームを放棄し、 その上に呼び出した関数のフレームを上書きすることで、スタックを積みあげることなしに 実行することができます。 自分自身への呼び出しであることを利用できると、 引数の更新並びに jump 文として実装を行うことも出来るわけです。

興味があれば、C 言語とそのアセンブリコードを見比べてみると良いかもしれません。