每个递归算法都是分治算法吗？

Question

我是一个有用的助手，可以翻译文本。

我有一个作业问题，需要使用分治算法来解决。

我通过递归解决了这个算法。我使用递归自动使用了分治吗？

例如，下面的方法是否为分治算法？因为我在fun中使用了fun函数（递归调用）。

代码：

    #include <stdio.h>

/* int a[] = {-6,60,-10,20}; */
int a[] =  {-2, -3, 4, -1, -2, 1, 5, -3};
int len = sizeof(a)/sizeof(*a);
int maxherearray[10];

int fun(int n);
int max(int a, int b);
int find_max(int a[], int len);
void print_array(int a[], int start_idx, int end_idx);

int start_idx = 0;  // Start of contiguous subarray giving max sum
int end_idx = 0;    // End of contiguous subarray giving max sum

#define NEG_INF (-100000)

int max_sum = NEG_INF;  // The max cont sum seen so far.

int main(void)
{
    start_idx = 0;
    end_idx = len - 1;
    maxherearray[0] = a[0];

    printf("Array a[]: ");
    print_array(a, 0, len-1);
    printf("\n");

    // Compute the necessary information to get max contiguous subarray
    fun(len - 1);
    printf("Max subarray value == %d\n", find_max(maxherearray, len));
    printf("\n");

    printf("Contiguous sums: ");
    print_array(maxherearray, 0, len - 1);
    printf("\n");

    printf("Contiguous subarray giving max sum: ");
    print_array(a, start_idx, end_idx);
    printf("\n\n");

    return 0;
}

int fun(int n)
{
    if(n==0)
        return a[0];

    int max_till_j = fun(n - 1);

    // Start of new contiguous sum
    if (a[n] > a[n] + max_till_j)
    {
        maxherearray[n] = a[n];

        if (maxherearray[n] > max_sum)
        {
            start_idx = end_idx = n;
            max_sum = maxherearray[n];
        }
    }
    // Add to current contiguous sum
    else
    {
        maxherearray[n] = a[n] + max_till_j;

        if (maxherearray[n] > max_sum)
        {
            end_idx = n;
            max_sum = maxherearray[n];
        }
    }

    return maxherearray[n];
}

int max(int a, int b)
{
    return (a > b)? a : b;
}

// Print subarray a[i] to a[j], inclusive of end points.
void print_array(int a[], int i, int j)
{
    for (; i <= j; ++i) {
        printf("%d ", a[i]);
    }
}

int find_max(int a[], int len)
{
    int i;
    int max_val = NEG_INF;
    for (i = 0; i < len; ++i)
    {
        if (a[i] > max_val)
        {
            max_val = a[i];
        }
    }

    return max_val;
}

- termit termit

---

不一定。如果您解释问题和算法，我们可能能够回答。 - Henry

@Henry，我编辑了这篇文章，请你看一下问题是否已经解决？ - termit termit

当你将原始问题分成两个较小的问题，解决它们并合并结果时，这就是分治算法。 - Eric

根据维基百科https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm#Divide_and_conquer，这是完全基于观点的问题，因为“‘分而治之’的名称有时被应用于将每个问题减少到仅一个子问题的算法”，因此您需要澄清您的学校使用的定义。否则，只需争论“我将问题分成了两部分{n} {0,...n-1}并为{n}内联了微不足道的情况 - 因此这显然是分而治之”。 :) - Alexei Levenkov

二分查找可以是递归的，并且根据任何定义都不是“分而治之”。 - Mooing Duck

Answer 1

每个递归函数不一定都是分治算法。还有其他方法，如减少并征服(通过恒定因子减少，递减1，可变大小递减)。

下面这种方法是分治算法吗？

你的函数正是采用每次减少一个常数的方法。你可以看一下这里。

求解最大子数组的分治算法伪代码：

MaxSubarray(A,low,high)
//
if high == low   
   return (low, high, A[low]) // base case: only one element
else
   // divide and conquer
   mid = floor( (low + high)/2 )
   (leftlow,lefthigh,leftsum) = MaxSubarray(A,low,mid)
   (rightlow,righthigh,rightsum) = MaxSubarray(A,mid+1,high)
   (xlow,xhigh,xsum) = MaxXingSubarray(A,low,mid,high)
   // combine
   if leftsum >= rightsum and leftsum >= xsum
      return (leftlow,lefthigh,leftsum)
   else if rightsum >= leftsum and rightsum >= xsum
      return (rightlow,righthigh,rightsum)
   else
      return (xlow,xhigh,xsum)
   end if
end if

--------------------------------------------------------------

MaxXingSubarray(A,low,mid,high)
// Find a max-subarray of A[i..mid]
leftsum = -infty
sum = 0
for i = mid downto low
    sum = sum + A[i]
    if sum > leftsum
       leftsum = sum
       maxleft = i
    end if
end for
// Find a max-subarray of A[mid+1..j]
rightsum = -infty
sum = 0
for j = mid+1 to high
    sum = sum + A[j]
    if sum > rightsum
       rightsum = sum
       maxright = j
    end if
end for
// Return the indices i and j and the sum of the two subarrays
return (maxleft,maxright,leftsum + rightsum)

-----------------------------------------------------------

=== Remarks:

(1) Initial call: MaxSubarray(A,1,n)

(2) Divide by computing mid.
    Conquer by the two recursive alls to MaxSubarray.
    Combine by calling MaxXingSubarray and then determining
       which of the three results gives the maximum sum.

(3) Base case is when the subarray has only 1 element.

- Soner from The Ottoman Empire

Answer 2

不一定。如果你探索函数式编程范式，你会学到简单的 for 循环可以被递归替代。

for i in range(x):
    body(i)

更改为

def do_loop(x, _start=0):
    if _start < x:
         body(_start)
         do_loop(x, _start=_start+1)

很明显，并非每个迭代都是分治算法。

- Jatentaki

---

在我编辑的帖子中，这是分治算法吗？ - termit termit