比較鴻溝，並用遞歸

Question

征服當我們談論的是分而治之，我們總是用遞歸.I've已知的分而治之的算法設計的技術，但我得到了一個問題：

是否所有分而治之算法遞歸，或者換句話說，是所有遞歸中使用的分而治之思想？

我很困惑。

Answer 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);