recursion - 比较分而治之与递归

Question

当我们谈论分而治之时，我们总是使用递归。我已经知道分而治之是一种算法设计技术，但我有一个问题：

所有分而治之的算法都是递归的，或者换句话说，分而治之的思想在所有的递归中都有使用吗？

我很困惑 。

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