再帰と反復

Question

反復を使用するすべての問題は反復を使用して解決できますが、再帰を使用して問題を解決できると思いますか？再帰は常に反復を代用できますか？可能であれば、答えに証拠を提示してください。無限のスタックがあると仮定するか、チューリングマシンでプログラムを実行します。私はこの証拠が理論的証拠であるかどうかは気にしない。 （これが私がチューリングマシンに言及した理由です）

Answer 1

はい、再帰は常に反復を置き換えることができます。これについては、beforeで説明しました。リンクされたポストからの引用：

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

ビットを説明する：計算可能な問題はチューリングマシンで解決できることがわかりました。また、再帰なしでプログラミング言語Aを構築することも可能です。これはチューリングマシンと同等です。同様に、プログラミング言語Bを反復せずに作成することも可能で、計算能力はチューリングマシンと同等です。

したがって、AとBの両方がTuring-completeである場合、任意の反復プログラムでは等価な再帰プログラムが存在しなければならないと結論付けることができます。これは理論上の結果です。つまり、任意の反復プログラムから1つの再帰プログラムを派生させる方法のヒントは得られません。逆もまた同様です。

Answer 2

はい。 tail recursionと呼ばれる再帰のタイプがあります。これは、繰り返しに直接変換できます。 1つは問題なく他のものに変換できます。したがって、すべての反復解を再帰解に変換することができます。

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

Answer 3

ループが不要な場合に再帰を使用する必要がありますが、その方法は特定のケースで繰り返しなければなりません。たとえば、フォルダを圧縮します。サブフォルダがある場合は、それ自体を呼び出す必要があります（再帰的）。あなたが望むなら、再帰は反復を置き換えることができますが、推薦されません。ほとんどの人は反復を使用して、必要なときだけ再帰を使用します。