繰り返しの繰り返しを選択する必要がありますか？

Question

解決策がどちらのケースでも同じ時間複雑さを持つが、反復のための空間複雑性が優れている場合、反復を繰り返し選択する理由は何ですか？

Answer 1

一部のアルゴリズムでは反復を理解することがより困難です。自然に再帰的に表現できるアルゴリズムは、繰り返し表現すると分かりにくいかもしれません。再帰アルゴリズムを反復アルゴリズムに変換することも困難であり、アルゴリズムが同等であることを検証することも困難な場合があります。

再帰では、各関数呼び出しで追加の自動オブジェクトを割り当てることができます。反復的な代替策は、メモリブロックを繰り返し動的に割り当てるかまたはサイズ変更することである。多くのプラットフォームでは、自動割り当てはスピードボーナスが再帰呼び出しの速度ペナルティとストレージコストを上回るという点ではるかに高速です。 （ただし、上記のように大量の自動データの割り当てはサポートされていないため、トレードオフです）

再帰は、スタックを使って再帰をシミュレートする必要がある場合に非常に有効です。再帰はコンパイラが既にスタックを管理していることを確認し、必要なものを正確に達成します。独自の管理を開始するときには、回避しようとしていた関数呼び出しオーバーヘッドを再導入する可能性が高いだけでなく、バグのない形ですでに存在しているホイール（バグのための十分なスペースを持つ）を再発明しています。

Answer 2

ここでは、特別な考慮が必要な場合の特定の例を示します。ツリー検索アルゴリズムは、（ツリーの各サブツリーがツリーであるため）再帰的に、または反復的に（スタックを使用して）定義できます。しかし、再帰的検索は、特定のプロパティを持つ最初のリーフを検索したり、すべてのリーフを検索したりするのには完全に機能しますが、リーフを返すオブジェクトや関数の状態、繰り返されるデザインでは、検索スタックはオブジェクトまたは関数の静的メンバーとして格納できますが、再帰的なデザインでは、関数が返ってきたときにコールスタックが失われ、再作成が困難または高価になります。