algorithm - 再帰と反復

Question

反復ロジックを持つすべての問題は反復を使用して解決できると思いますが、再帰を使用して問題を解決できるでしょうか? 再帰は常に反復を置き換えることができますか? できれば回答の根拠を示してください。また、無限のスタックがあるか、チューリング マシンでプログラムを実行するとします。この証明が理論的証明であるかどうかは気にしません。（それがチューリングマシンについて言及した理由です）

Answer 1

はい、再帰は常に繰り返しを置き換えることができます。これについては以前に説明しました。リンクされた投稿からの引用：

厳密に反復構造を使用してチューリング完全言語を構築し、再帰構造のみを使用してターニング完全言語を構築できるため、この 2 つは等価です。

少し説明します。計算可能な問題はチューリング マシンで解決できることがわかっています。Aそして、チューリングマシンと同等の再帰を使わないプログラミング言語を構築することが可能です。同様にB、チューリング マシンと同等の計算能力を備えたプログラミング言語を、繰り返しなしで構築することも可能です。

したがって、 と の両方がチューリング完全である場合A、B反復プログラムには同等の再帰プログラムが存在する必要があり、その逆も成り立つと結論付けることができます。これは理論上の結果であり、任意の反復プログラムから 1 つの再帰プログラムを導出する方法、またはその逆の方法についてのヒントを提供しないという意味です。

Answer 2

はい。反復に直接変換できる末尾再帰と呼ばれる再帰のタイプがあります。片方は問題なく変換できます。したがって、すべての反復ソリューションは再帰ソリューションに変換できます。

実際、多くのコンパイラは、末尾再帰を実行していることを検出し、効率のために for ループ タイプのコードに変換できます。

Answer 3

ループが不要な場合は再帰を使用する必要がありますが、特定のケースではメソッド自体を繰り返す必要があります。たとえば、フォルダを圧縮します。サブフォルダーがある場合は、それ自体を呼び出す必要があります (再帰的)。必要に応じて再帰を繰り返しに置き換えることもできますが、お勧めしません。ほとんどの人は反復のみを使用し、必要な場合にのみ再帰を使用します。