反復除算と征服アルゴリズム

Question

私は、反復アルゴリズムを使用して再帰アルゴリズムを使用して、除算と征服のアプローチではなくを使用してアルゴリズムを作成しようとしています。

私はループに近づく方法について混乱しています。

ベースケースにヒットするまで、問題を小さな問題に分割する必要があります。私はこれがまだ当てはまると仮定していますが、より大きな問題を解決するために小さなサブプログラムをどのように（再帰なしで）使うことができるか分かりません。

たとえば、（1次元空間で - 私はこれを自分自身で高次元に一般化しようとしますが）最も近い点のペアを見つけるアルゴリズムを考え出しています。もしLが整数の座標であるnearest_pair（L）を持っていたら、ℝに分割し、この問題を解決できるITERATIVEアルゴリズムを克服するにはどうすればいいでしょうか？

（一般性を失うことなく、私は、Pythonを使用しています）

Answer 1

反復アルゴリズムに任意の再帰アルゴリズムを有効にする安価な方法は、再帰関数を取るループに入れ、そしてあなた自身のスタックを使用することです。これにより、関数呼び出しのオーバーヘッドがなくなり、不要なデータがスタックに保存されることがなくなります。しかし、これは通常、「最良の」アプローチではありません（「ベスト」は問題と文脈によって異なります）。

あなたの問題を言いましたが、それはリストをサブリストに分解し、それぞれの中で最も近いペアを選び、それらの2つの結果から最も近いペアを取る。これを繰り返し行うには、上記の一般的な方法よりも、これにアプローチするより良い方法は、逆の方法をとることです：サイズ3のリスト（見て3つのペアがあります）を見てそこから上に向かいます。サイズ2のリストは自明であることに注意してください。

最後に、座標が整数の場合、それらはZ（Rのサブセットのほうがずっと小さい）にあります。