recursion - 分割統治法と再帰を比較してください

Question

分割統治について話しているときは、常に再帰を使用します。分割統治はアルゴリズム設計の手法であることはすでに知っていますが、1つの質問があります。

すべての分割統治アルゴリズムの再帰ですか、または別の言い方をすれば、分割統治の考え方はすべての再帰で採用されていますか？

よくわかりません 。

Answer 1

私があなたの問題を正しく理解していれば..すべての分割統治アルゴリズムは本質的に再帰的ですか？はい！

定義により

実際に分割統治アルゴリズムを適用するには、次の3つのステップがあります。

• 問題を1つ以上のサブ問題に分割します。
• サブ問題を再帰的に解決することにより、サブ問題を克服します。ただし、サブ問題のサイズが十分に小さい場合は、簡単な方法でサブ問題を解決してください。
• サブ問題の解決策を元の問題の解決策に結合します。

しかし、実装部分に関心がある場合は、再帰（よりエレガントでシンプルですが）が唯一の方法ではありません。

二分探索は分割統治パラダイムのよく知られた例であり、ここにアルゴリズムの反復実装があります。

//binary search for x, in array A[1 .. N]

min := 1;
max := N;
repeat
  mid := (min+max) div 2;
  if x > A[mid] then
    min := mid + 1;
  else
    max := mid - 1;
until (A[mid] = x) or (min > max);