1

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

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

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

4

3 回答 3

2

嵌入代码注释：

    // 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-23T02:03:22.633 回答
0

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

于 2013-09-23T02:04:19.663 回答
0

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

于 2013-09-23T02:05:37.730 回答