recursion - TCOを実装する言語での末尾再帰の再帰深度に制限しますか？

Question

末尾呼び出しの最適化を実装する言語での再帰の深さに対する理論的/実際的な制限は何ですか？（繰り返し関数が適切に末尾呼び出しされていると想定してください）。

私の推測では、再帰的な手順であるにもかかわらず、再帰的なプロセスがないため、理論上の制限はNONEです。実際の制限は、使用可能なメインメモリによって許可される制限です。私がどこか間違っている場合は、明確にするか修正してください。

Answer 1

末尾再帰関数が最適化されると、本質的に反復関数になります。コンパイラーは、元の呼び出しのスタックフレームを後続の呼び出しに再利用するため、スタックスペースが不足することはありません。ヒープメモリ（または、スタック上にない他の種類のメモリ）を割り当てていない場合は、無限に深くなる可能性があります（十分な忍耐力がある限り;））再帰（無限と考えてください）ループ;同じ特性を持っています）。

要約すると、実際的な制限はありません。

Answer 2

@Mehrdad Afshariが書いたことに加えて、末尾再帰（またはより一般的には末尾呼び出しのチェーン）が潜在的に無限であることが実際に非常に重要であることを指摘したいと思います。そうしないと、Webサーバーを作成できなかったからです。オペレーティングシステム、インタプリタ、REPL、または関数型言語での実際にはあらゆる種類のイベント処理ループ。

結局のところ、オペレーティングシステムは無限ループに他ならず、関数型言語でループを作成する方法は末尾再帰を使用することです。末尾再帰が無限でなければ、ループは無限ではありません。したがって、オペレーティングシステムを作成できるだけでなく、言語はチューリング完全ではありません。

基本的に、これは関数型言語でWebサーバーを作成する方法です。

def loop(queue) = {
  // handle first request in queue
  loop(queue)
}

無限末尾再帰がないと、これはすぐにメモリを使い果たしてしまいます。