[解決済み] テールコール最適化とは何ですか？

質問

簡単に言うと、テールコール最適化とは何ですか？

具体的には、どのような小さなコードに適用できるのか、また適用できないのか、その理由も含めて教えてください。

解決方法は？

テールコール最適化とは、呼び出す関数が呼び出された関数から取得した値を返すだけなので、関数のために新しいスタックフレームを確保することを避けることができる、というものです。最も一般的な使用方法は末尾再帰で、末尾呼び出し最適化を利用するように書かれた再帰関数は、一定のスタック領域を使用することができます。

Schemeは、どんな実装でもこの最適化を提供しなければならないと仕様で保証している数少ないプログラミング言語の一つです。そこで、Schemeの階乗関数の例を二つ紹介します。

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

最初の関数は末尾再帰的ではありません。なぜなら、再帰的な呼び出しが行われたとき、関数は呼び出しが返った後の結果に対して行う必要のある乗算を追跡しておく必要があるからです。そのため、スタックは次のようになる。

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

一方、末尾再帰的階乗のスタックトレースは次のようになる。

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

ご覧のように、fact-tailを呼び出すたびに同じ量のデータを記録しておけばよいのです。なぜなら、取得した値をそのままトップに返しているだけだからです。つまり、(fact 1000000)を呼び出すとしても、(fact 3)と同じ量のスペースしか必要ないのです。これは、tail-recursiveでないfactの場合とは異なり、大きな値ではスタック・オーバーフローが発生する可能性があります。