scheme - スキームの再帰関数は常に末尾呼び出し最適化されていますか?

Question

Scheme の末尾呼び出しの最適化について読んだことがあります。しかし、テールコールの概念を理解しているかどうかはわかりません。次のようなコードがある場合:

(define (fac n)
  (if (= n 0)
      1
      (* n (fac (- n 1)))))

これを最適化して、スタックメモリを消費しないようにすることはできますか? または、末尾呼び出しの最適化を次のような関数にのみ適用できます。

(define (factorial n)
    (let fact ([i n] [acc 1])
      (if (zero? i)
          acc
          (fact (- i 1) (* acc i)))))

score 10 · Accepted Answer

テールコールについて考える便利な方法は、「再帰的なプロシージャコールの結果はどうなるか」ということです。

への内部呼び出しの結果facを使用し、を掛けてnへの呼び出し全体の結果を生成する必要があるため、最初の関数は末尾最適化できませんfac。

ただし、2 番目のケースでは、への「外部」呼び出しfactの結果は... への内部呼び出しの結果ですfact。他に何もする必要はなく、後者の値は関数の値として直接渡すことができます。つまり、他の関数コンテキストを保持する必要がないため、単純に破棄できます。

R5RS 標準では、テールコンテキストの概念を使用して「テールコール」を定義しています。

score 4 · Accepted Answer

いいえ、最初のfacものは最適化できません。

fac関数が呼び出されたとき、呼び出しが完了したらその場所に戻り、呼び出しの結果を将来の計算 (関数)で使用できるように、関数が呼び出された場所を知る必要があります。

fact実装方法が異なります。最後に行うことfactは、自分自身を呼び出すことです。呼び出し元の場所を覚えておく必要はありません — 代わりに、テールコールの除去を実行できます。fact返品後に行うべきその他のアクションはありません。

2 に答える 2