TCOを実装する言語で末尾再帰の再帰深度に制限はありますか？

Question

テールコールの最適化を実装する言語での再帰の深さに対する理論的/実用的な制限はありますか？ （繰り返し機能が正しく呼び出されたと仮定してください）。

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

Answer 1

テール再帰関数を最適化すると、基本的に反復関数になります。コンパイラは、以降の呼び出しで元の呼び出しのスタックフレームを再利用するため、スタック領域が不足することはありません。 ヒープメモリ（またはスタックにない他の種類のメモリ）を割り当てていない場合は、、あなたは無限に深く（あなたが十分に辛抱強くいる限り）再帰することができます無限ループ、同じ特性を持っています）。

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

Answer 2

@Mehrdad Afshariが書いたことに加えて、尾部の再帰（またはより一般的には尾部呼び出しの連鎖）が潜在的に無限になることが実際には非常に重要であることを指摘したいと思います。オペレーティングシステム、インタプリタ、REPL、または実際にはあらゆる種類のイベント処理ループを関数型言語で記述することができます。結局のところ、オペレーティングシステムは無限ループに過ぎず、関数言語でループを書く方法は末尾再帰を使用しています。尾の再帰が無限でなければ、ループは無限ではありません。したがって、あなたはオペレーティングシステムを書くことができないだけでなく、その言語はTuring-completeでさえありません。

これはあなたが関数型言語でWebサーバを書く方法です基本的には、：

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

無限末尾再帰がなければ、これはすぐにメモリ不足になります。