反復を使用するすべての問題は反復を使用して解決できますが、再帰を使用して問題を解決できると思いますか?再帰は常に反復を代用できますか?可能であれば、答えに証拠を提示してください。無限のスタックがあると仮定するか、チューリングマシンでプログラムを実行します。私はこの証拠が理論的証拠であるかどうかは気にしない。 (これが私がチューリングマシンに言及した理由です)再帰と反復
再帰と反復
答えて
はい、再帰は常に反復を置き換えることができます。これについては、beforeで説明しました。リンクされたポストからの引用:
厳密な反復構造と再帰構造のみを使用した完全な言語を使用してチューリング完全言語を構築できるため、2つは同等です。
ビットを説明する:計算可能な問題はチューリングマシンで解決できることがわかりました。また、再帰なしでプログラミング言語A
を構築することも可能です。これはチューリングマシンと同等です。同様に、プログラミング言語B
を反復せずに作成することも可能で、計算能力はチューリングマシンと同等です。
したがって、A
とB
の両方がTuring-completeである場合、任意の反復プログラムでは等価な再帰プログラムが存在しなければならないと結論付けることができます。これは理論上の結果です。つまり、任意の反復プログラムから1つの再帰プログラムを派生させる方法のヒントは得られません。逆もまた同様です。
このリンクを見逃してしまった –
はい。 tail recursionと呼ばれる再帰のタイプがあります。これは、繰り返しに直接変換できます。 1つは問題なく他のものに変換できます。したがって、すべての反復解を再帰解に変換することができます。
実際、多くのコンパイラは、末尾再帰を実行していることを検出して、それを効率のためにforループ型コードに変換できます。
ループが不要な場合に再帰を使用する必要がありますが、その方法は特定のケースで繰り返しなければなりません。たとえば、フォルダを圧縮します。サブフォルダがある場合は、それ自体を呼び出す必要があります(再帰的)。あなたが望むなら、再帰は反復を置き換えることができますが、推薦されません。ほとんどの人は反復を使用して、必要なときだけ再帰を使用します。
- 1. 再帰、テール再帰と反復
- 2. 反復/非再帰マージソート
- 3. XSLT反復または再帰のパフォーマンス
- 4. 再帰的Vs反復的BSTのトラバーサル
- 5. ビンゴとしての反復関数への再帰関数
- 6. 約束と再帰でのファイルディレクトリの反復
- 7. 再帰的メソッドと標準的な反復メソッド
- 8. 反射と再帰 - StackOverflowExceptionが
- 9. MIPSコードの再帰的反復文字列の複雑さ
- 10. リスト/配列を再帰的に反復する
- 11. 再帰的にネストされたPython辞書を反復する
- 12. 入れ子配列のPHP再帰的反復
- 13. bashスクリプト - 2つのディレクトリに再帰的に反復する
- 14. 再帰的なCTE取得全部の反復からの親
- 15. Pythonでオブジェクトを再帰的に反復する
- 16. Javascript JSONを反復する再帰関数のブレーク条件
- 17. mongoのpython辞書による再帰的反復
- 18. 再帰関数の反復に関する問題
- 19. 再帰的ツリーウォーキング関数を反復的に変換する
- 20. 反復メソッドを再帰的メソッド(Java)に変換する方法
- 21. Vuejs2 - "tr"要素を再帰的に反復する
- 22. 単一リンクリストでの単純な再帰的反復処理JavaScript
- 23. Tシャツのバリアントを反復する再帰関数
- 24. 反復を再帰Pythonに置き換える
- 25. 再帰的な反復可能なテンプレート関数C++
- 26. 反復子を使用したPHP分岐の再帰
- 27. ツリートラバーサル、再帰はPythonの反復よりも速いですか?
- 28. プロミスイテレータを反復する非再帰的メソッド
- 29. 動的プログラミング再帰的または反復的
- 30. Pythonでこの再帰関数を反復する方法は?
誰かがここで私を修正するかもしれませんが、いくつかの言語(純粋に関数型言語)ではありません*再帰に完全に基づいて*?例えばLisp言語? –
@TonyR Lisp言語はまったく機能的ではありません。 –
それでは "機能言語"はどうですか? –