c - 递归查找数组的最大元素

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) 次？

Answer 1

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

当你第一次开始时，n=5。它将占用 else 块（n 不是 1）。然后，您再次使用 n-1 (n=4) 调用最大值。再次，使用 else 块。

总而言之，该函数在 n 达到 1 之前被调用了 4 次，然后它使用 if 块并返回 ar[0]。

正如其他人所提到的，所编写的函数不会返回列表的最大值。奇怪的是，它似乎总是返回 5，除非列表数组大小为 1，在这种情况下，它返回该元素的值。

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

Answer 2

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

看一看：

从 main 我们用 5 调用最大值，然后在 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

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

Answer 4

实际上它只被调用了 4 次。

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

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

但是，这种递归还不够好。由于您的函数被调用 n-1 次，因此您只需支付递归的开销（例如堆栈），但与迭代相比没有任何优势。

如果你真的想要这个任务的递归，试着把数组分成 2 并将每一半传递给递归函数。

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

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

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