3

我有这个功能：

int max(int arr[], int size)
{
    size--;
    if(size > 0)
    {
        int max = max(arr, size);
        if(arr[max] > arr[size]) return max;
    }
    return size;
}

当然它有效。我的问题是 - 这是如何工作的？有人可以一步一步地解释我吗？现在是星期六，所以也许有人有一点时间：DI 特别是指 if 块中的这两行。

4

4 回答 4

2

让我们以这个数组为例：

int arr[] = { 42, 54, 23 };
max(arr, 3);

此函数通过检查当前元素的最大值与所有先前元素的最大值来工作。这是堆栈调用的表示：

max(arr, 3)
    max(arr, 2)
        max(arr, 1)
            return 0
        arr[0] (arr[max] = 42) <= arr[0] (arr[size] = 42) => return size (0)
    arr[0] (arr[max] = 42) <= arr[1] (arr[size] = 54) => return size (1)
arr[1] (arr[max] = 54) > arr[2] (arr[size] = 23) => return max (1)

注意：用相同的标识符命名变量和函数是个坏主意。

于 2013-01-19T14:24:07.163 回答
2

你的代码如下：

1 int max(int arr[], int size){
2     size--;
3     if(size > 0){
4         int max = max(arr, size);
5         if(arr[max] > arr[size]) return max;
6     }
7     return size;
8 }

您可以通过传递数组和该数组的大小（或长度）来调用它。

代码命中的第一个重要点是在第 4 行，它递归地调用自身。但请注意，在第 2 行，大小减少了 1。因此，您可以将 size 视为一个索引，该索引引用当前对函数的调用所考虑的数组元素。

这意味着最终，数组的大小将降至零，我们将查看数组的第一个元素。此时跳过第 3 行到第 6 行，返回 0。

当其中一个递归调用返回时，我们将回到第 4 行。

对于第一次返回，这意味着int max = 0;.

现在我们将第零个元素与第一个元素进行比较。我们返回较大的索引。下一个比较将在第二个元素和前两个元素中较大的一个之间进行。

这一直持续到所有递归调用都返回，此时最大元素的索引返回给调用函数。

请注意，return size;应将其替换为return 0以增加清晰度。

于 2013-01-19T14:28:18.227 回答
2

让我们逐步解决arr[] = [1,2]这意味着调用的问题max(arr[], 2)

size--; // 2-1 = 1
if(size > 0) //True
    {
        int max = max(arr, size); //Going into the recursive call

这是递归运行：

    size--; // Now 1-1 = 0
    if(size > 0) //False
    return size; //0 returned

现在回到调用函数：

        int max = 0 //From return
        if(arr[max] > arr[size]) //arr[0]>arr[1] which is false 
    }
    return size; //Now, control reaches here and 1 is passed back to the calling scope
}
于 2013-01-19T14:29:32.603 回答
2

在此处输入图像描述

抱歉，图表格式不佳

于 2013-01-19T14:45:04.130 回答