lisp - 末尾呼び出しと末尾再帰の違いは何ですか？

Question

末尾再帰は、関数がそれ自体に末尾呼び出しを行う特殊なケースであることを理解しています。しかし、末尾呼び出しと末尾再帰がどのように異なるのかわかりません。SchemeのようにTCO（末尾呼び出し最適化）が実装された「適切な末尾再帰」言語では、末尾呼び出しと末尾再帰がスタックやその他のリソースを消費しないことを意味します。コンパイラが末尾再帰を最適化できない言語では、プログラムがスタックを使い果たしてクラッシュする可能性があります。「適切な末尾再帰」言語では、ループを使用するよりも、ループの末尾再帰を実装する方が効率が悪いとは思いません。

Answer 1

最初に「テールコール」を明確にしましょう。

末尾位置の呼び出しは、その結果が外側の関数の値としてすぐに返される関数呼び出しです。テール位置は静的プロパティです。

末尾位置での呼び出しは、スタックに何もプッシュせずに実装できます。これは、古いスタック フレームが本質的に役に立たないためです (関数型言語では一般的に正しいが、C などでは必ずしもそうではないという仮定の下で)。Guy Steele が言ったように、テール コールは引数を渡すジャンプです。

大まかに言えば、言語実装は、末尾位置のすべての呼び出しをスタック成長なしのジャンプとして実装する場合と同じ漸近空間使用量を持つ場合、適切に末尾再帰的です。それは本当に大まかな単純化です。完全なストーリーが必要な場合は、Clinger のProper Tail Recursion and Space Efficiencyを参照してください。

末尾再帰関数を特別に処理するだけでは、適切な末尾再帰を実現するには不十分であることに注意してください(末尾呼び出しは特別に処理する必要があります)。用語はやや誤解を招くものです。

また、末尾呼び出しをジャンプとして実装せずに、その漸近的なスペース効率を達成する方法が他にもあることに注意してください。たとえば、それらを通常の呼び出しとして実装し、不要なフレームを (何らかの方法で) 削除して定期的にスタックを圧縮することができます。MTA でBaker's Cheney を参照してください。

Answer 2

あなたが言うように、末尾再帰は末尾呼び出しの特殊なケースです。したがって、一般的なTCOを自明に実装する言語は、「適切に末尾再帰」です。

ただし、その逆は成り立ちません。末尾再帰のみを最適化する言語はかなりあります。これは非常に簡単だからです。ループに直接変換でき、スタックを新しい方法で操作する特定の「末尾呼び出し」操作は必要ありません。たとえば、これが、末尾呼び出し命令を持たないJVMにコンパイルする言語が、通常、末尾（自己）再帰のみを最適化する理由です。（トランポリンなど、そのような指示の欠如を回避するためのテクニックがありますが、それらは非常に高価です。）

完全な末尾呼び出しの最適化は、自己（または相互）再帰呼び出しだけでなく、末尾位置にあるすべての呼び出しにも適用されます。特に、ターゲットが静的に認識されていない呼び出しに拡張されます。たとえば、ファーストクラスの関数や動的にディスパッチされたメソッドを呼び出す場合などです。その結果、それは幾分より精巧な（よく知られているが）実装技術を必要とします。

多くの関数型プログラミング手法（ただし、いくつかの一般的なOOパターン（たとえば、 FelleisenのECOOP'04プレゼンテーションまたはGuy Steeleのブログ投稿を参照））を実際に使用するには、完全なTCOが必要です。

Answer 3

どちらも「尻尾」という言葉が含まれているため、この 2 つは何らかの形で関連していますが、まったく異なるものです…</p>

末尾再帰は特定の制約のある再帰であり、末尾呼び出しは関数呼び出しです。あなたの質問は、「動物と猫の違いは何ですか?」に少し似ています…</p>

末尾呼び出しは、末尾位置での関数呼び出しです。例: f(x)in f(x)、およびg(★)ing(f(x)) 反例: f(x)in1+f(x)および ing(f(x))

末尾再帰は、再帰呼び出しが末尾呼び出しである再帰です。例: f(★)"=" 記号の右側で、f(x) = f(x)末尾f(x,y) = if x == 0 then y else f(x-1,y+x) 呼び出しで自分自身を呼び出す 2 つの再帰関数を定義しました。それでおしまい。

TCO のある言語では、末尾の呼び出しにコストがかからないため、(末尾の) 再帰は一定のスタックで機能し、誰もが満足します。