recursion - 再帰とループ

Question

ここに示すように、ツリーの例を使用して作業を試みています: http://cslibrary.stanford.edu/110/BinaryTrees.html これらの例はすべて、再帰によって問題を解決します。つまり、再帰によって解決できる問題には、一般に反復的な解決策があることを常に確認できます。そうでない場合、再帰/反復によってのみ解決できる問題を示すために、どのような例を挙げることができますか?

--

Answer 1

コンピューターでの反復と再帰の唯一の違いは、組み込みスタックとユーザー定義スタックのどちらを使用するかです。したがって、それらは同等です。

Answer 2

私の経験では、ほとんどの再帰的ソリューションは実際に反復的に解決できます。

また、再帰的なソリューションではメモリと CPU の消費量のオーバーヘッドが大きくなりすぎる可能性があるため、これも有効な手法です。

Answer 3

再帰は各呼び出しに関する情報を格納する暗黙のスタックを使用するため、いつでもそのスタックを自分で実装して、再帰呼び出しを回避できます。そうです、すべての再帰的ソリューションは反復ソリューションに変換できます。

証明のためにこの質問を読んでください。

Answer 4

再帰と反復は、非常に基本的なレベルで同じことを行う 2 つのツールです。つまり、定義された一連の値に対して繰り返し操作を実行します。どちらか一方だけで解決できない問題はないという点で、それらは交換可能です。ただし、どちらか一方が他方よりも適しているというわけではありません。

Answer 5

「老人」として、私は再帰降下パーサーの方が書きやすいが、スタックベースの反復パーサーの方がパフォーマンスが優れていることを学んだ記憶に戻ります。メトリクスでその考えをサポートしているように見える記事は次のとおりです。

http://www.texttoolkit.com/index.php?option=com_content&view=article&catid=35%3Atechnology&id=60%3Abeyond-recursive-descent&Itemid=55

注意すべきことの 1 つは、再帰降下でコール スタックをオーバーランするという著者の言及です。反復的なスタックベースの実装は、リソースの効率を大幅に向上させることができます。

Answer 6

再帰には、既知の終了なしで継続するという利点があります。この完璧な例は、調整され、スレッド化されたクイック ソートです。

追加のループを生成することはできませんが、再帰によって新しいスレッドを生成できます。