以递归方式查找数组的最大元素

考虑这段代码,它计算数组的最大元素。

#include  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)次?

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

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

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

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

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

这就是编码做的……

看一看:

从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 

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

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

实际上只召唤了4次。

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

因此,其他部分被称为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)); } 
 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; }