递归查找数组中的最大元素

Question

考虑以下代码，它计算数组中的最大元素。

#include <stdio.h>

int maximum(int arr[], int n)
{
    if (n == 1) {
        return arr[0];
    } else {
        int max = maximum(arr, n-1);
        printf("Largest element : %d\n", max);
        return 5; // return arr[n-1] > max ? arr[n-1] : max;
    }
}

int main()
{
    int array[5] = {5, 23, 28, 7, 1};
    printf("Maximum element of the array is: %d", maximum(array, 5));
    return 0;
}

为什么else代码块会被调用四(4)次？

- user762630

---

当我运行它时，它只被调用了4次。 - huon

为什么称它被调用4次很让人惊讶？你期望会是什么？ - huon

@JohnBode：因为我预计程序流程会在else块中的第一个return之后返回到主程序。 - user762630

@Erdem 看看那个 else 块...在那个“第一个返回”之前（它将返回到主函数），你再次调用了 maximum()。这意味着“第一个返回”实际上是递归列表中最后被调用的。如果您使用符号调试器并逐行查看代码，您可能会更好地理解它。 - mah

@JimBalter：我的意思是，如果我注释掉递归函数int max = maximum(ar, n-1);，那么它只会被调用一次。 - user762630

Answer 1

该函数是递归的，因此它将被多次调用。

当您开始时，n = 5。它将使用else块（n不等于1）。 然后，您再次使用n-1（n = 4）调用maximum。 再次采取else块。

总之，在n达到1之前，该函数将被调用4次，然后采取if块并返回ar [0]。

正如其他人所提到的，根据目前的代码，该函数将不会返回列表的最大值。有趣的是，除非列表数组大小为1，否则它似乎总是返回5，并返回该元素的值。

相反，递归方法通常涉及每次将列表分成两半，然后在列表最终分成一对元素时返回每对的最大值。

- Kevin

Answer 2

这就是它编码的目的...

看一下：

从主函数中我们用5调用了maximum函数，然后在else语句中我们使用n-1再次调用了该函数。

maximum(array, 5)  //first call from main, hit the else n=5, so recall with n-1
maximum(ar, 4)     //second call from maximum, hit the else n=4, so recall with n-1
maximum(ar, 3)     //third call from maximum, hit the else n=3, so recall with n-1
maximum(ar, 2)     //fourth call from maximum, hit the else n=2, so recall with n-1
maximum(ar, 1)     //fifth call from maximum, n==1 now so do the if and return 5

- Mike

Answer 3

一种可能的递归解决方案是比较前一个元素和当前元素。

#include <stddef.h>

static int max(int a, int b) {
    return a > b ? a : b;
}
int max_array(int *p, size_t size)
{
    if (size > 1)   return max(p[size-1], max_array(p, size-1));
    else            return *p;
}

- md5

Answer 4

实际上只调用了4次。

递归规则，如您所声明的： 如果n==1，则返回ar [0]，否则返回n-1个元素中的最大值。

因此，else部分被调用了5、4、3和2次。

然而，这种递归不够好。由于您的函数被调用了n-1次，您只支付了递归的开销（例如堆栈），但在迭代方面并没有任何优势。

如果您真的想要为此任务使用递归，请尝试将数组分成两半，并将每半传递给递归函数。

简单的伪代码（不正确地处理奇数）：

int max(int arr[], int n)
{
    if (n<=1)
        return arr[0];
    return MAX(max(arr, n/2), max(arr+n/2, n/2));
}

- eyalm

---

将其分成两部分有什么好处吗？如果您将任务拆分并将每个任务分配给单独的线程，您可能会利用到多余的处理器，但如果没有这样做，它只会使代码变得更加复杂，而没有任何好处。 - mah

我同意，但那不是问题所在。我的答案旨在表明在这里使用递归是没有意义的，并且更好的方法是使用递归（例如在qsort中）。无论如何，在这个解决方案中，堆栈深度为O(log n)。 - eyalm

我之前没有考虑过堆栈深度...这是一个很好的优点。 - mah

嗯...我做了一些基准测试，似乎需要比自然解决方案更多的递归。 - md5

1. 当 n 为奇数时，此处会失败。应该使用 MAX(max(arr, n/2), max(arr+n/2, n-n/2))。
2. 最好使用 size_t n。
3. 如果 MAX() 是宏，可能会调用额外的函数。请参见 http://stackoverflow.com/a/25414877/2410359。

- chux - Reinstate Monica

Answer 5

int maximum(int ar[], int n)
{
  int max;
  if(!n)
    return ar[n];
  max =maximum(ar,n-1);
  return ar[n]>max?ar[n]:max;
}

- perilbrain