algorithm - スタック フレームの使用が避けられない (完全に末尾再帰にすることができない) 再帰関数/アルゴリズムはありますか?

Question

大量のスタック メモリの使用を回避する方法で書き換えることができない再帰アルゴリズム/関数の例を考え出そうとしています (つまり、完全に末尾再帰にすることも、スタックを使用しないループを使用して書き換えることもできません)。そのような機能は存在しますか？

クイックソートが候補になるかもしれませんが、単一の末尾再帰関数呼び出しを使用するように書き直すことができるかどうかはわかりません。

Answer 1

一般的なケースで複数の呼び出しを必要とするすべてのアルゴリズムは、最初の呼び出しが末尾の位置になく、常に継続があるため、反復またはスタックの成長のためのバックトラック スタックなしでは実行できません。

単純なフィボナッチ、クイックソート、ツリーの合計はすべてそのカテゴリに含まれます。