分而治之递归

我只是想了解递归在这个例子中是如何工作的，并且如果有人能够为我分解这个，我将不胜感激。我有以下的算法基本上返回最大数组中的元素：分而治之递归

int MaximumElement(int array[], int index, int n) 
    { 
     int maxval1, maxval2; 
     if (n==1) return array[index]; 
     maxval1 = MaximumElement(array, index, n/2); 
     maxval2 = MaximumElement(array, index+(n/2), n-(n/2)); 
     if (maxval1 > maxval2) 
      return maxval1; 
     else 
      return maxval2; 
    }

我无法理解的递归调用在这里是如何工作的。第二次调用时，第一次递归调用是否总是被执行？我真的很感激，如果有人可以请向我解释这一点。非常感谢！嵌入式

来源

2013-09-23 acc_so

这是我假设的C++吗？ –

没有特定的编程语言。我只是想了解这个方法/函数/伪代码背后的概念。我有一个Java背景。 –

在Java中，你可能不会使用'int n'参数（但你可以）。 –

代码注释：

// the names index and n are misleading, it would be better if we named it: 
    // startIndex and rangeToCheck 
int MaximumElement(int array[], int startIndex, int rangeToCheck) 
{ 
    int maxval1, maxval2; 

    // when the range to check is only one cell - return it as the maximum 
    // that's the base-case of the recursion 
    if (rangeToCheck==1) return array[startIndex]; 
    // "divide" by checking the range between the index and the first "half" of the range 
    System.out.println("index = "+startIndex+"; rangeToCheck/2 = " + rangeToCheck/2); 
    maxval1 = MaximumElement(array, startIndex, rangeToCheck/2); 
    // check the second "half" of the range 
    System.out.println("index = "+startIndex+"; rangeToCheck-(rangeToCheck/2 = " + (rangeToCheck-(rangeToCheck/2))); 
    maxval2 = MaximumElement(array, startIndex+(rangeToCheck/2), rangeToCheck-(rangeToCheck/2)); 

    // and now "Conquer" - compare the 2 "local maximums" that we got from the last step 
    // and return the bigger one 
    if (maxval1 > maxval2) 
     return maxval1; 
    else 
     return maxval2; 
}

使用示例：

int[] arr = {5,3,4,8,7,2}; 
int big = MaximumElement(arr,0,arr.length-1); 
System.out.println("big = " + big);

输出：

index = 0; rangeToCheck/2 = 2 
index = 0; rangeToCheck/2 = 1 
index = 0; rangeToCheck-(rangeToCheck/2 = 1 
index = 0; rangeToCheck-(rangeToCheck/2 = 3 
index = 2; rangeToCheck/2 = 1 
index = 2; rangeToCheck-(rangeToCheck/2 = 2 
index = 3; rangeToCheck/2 = 1 
index = 3; rangeToCheck-(rangeToCheck/2 = 1 
big = 8

来源

2013-09-23 02:03:22 alfasin

我了解基本情况。我试图理解递归调用，但我不明白它是如何工作的。例如：你有一个大小为6（2,4,1,3,5,6）的数组。递归调用如何工作？第一个调用是maxva1l = MaximumElement（array，0，6/2），第二个调用变为（maxval1 = MaximumElement（array，0，3/2）？ –

@acc_so你必须更具体一些... – alfasin

我很抱歉！我试图问的是，该片段如何处理值为{2,4,1,3,5,6}的大小为6的数组？感谢很多!!那就是：不是输出看起来像，但递归调用的每一步是如何工作的也许，一个大小为4的数组可能很容易解释 –

这到底是怎么发生的是均为递归调用正在一个接一个地进行。第一个搜索有数组并返回最大值，第二个搜索另一半并返回最大值。然后比较两个最大值，并返回更大的最大值。

来源

2013-09-23 02:04:19

非常感谢回复！ –

是的。你猜到的是对的。在两个递归调用MaximumElement(array, index, n/2)和MaximumElement(array, index+(n/2), n-(n/2))中，重复执行第一个调用，直到调用数组的单个元素。然后将这两个元素进行比较，并返回最大值。然后继续这个比较过程直到返回最大的元素。

来源

2013-09-23 02:05:37 Deepu

这就是我最初的理解，但是在所有比较都是ma之前，不会终止程序德？ –

否。返回将仅终止一个特定的函数调用执行。其他函数调用将被执行。 – Deepu

请稍微详细一点！： - ）你能用一个简单的例子来解释递归吗？就像有4个值的数组？ –

分而治之递归

回答

相关问题