c - 使用递归查找数组中的最大值

Question

我想通过递归找到数组中的最大数，这段代码有什么问题。

 #include<stdio.h>
int find_max(int *a,int n){
    int m_max;
    if(n==1){
        return a[0];
    }
    m_max=find_max(a,n-1);
    if(a[n-1]>m_max)
        m_max=a[n-1];
}

Answer 1

1. 正如@moffeltje 评论的那样，“当 n != 1 时没有返回”

     if(a[n-1]>m_max) 
       m_max=a[n-1];
     return m_max;  // add
   }
   

2. 这种线性方法给递归带来了坏名声。如果有n数，最大递归深度为n .最好将其一分为二以获得最大深度 log2(n)

   int find_max(const int *a, int n) {
     if (n <= 1) {
       return a[0];
     }
     int left = find_max(a, n/2);
     int right = find_max(&a[n/2], n - n/2);
     return left > right ? left : right;
   }
   

--- 次要内容如下

1. 处理边界情况，其中 n < 1或 a == NULL .

   int find_max(const int *a, int n) {
     if (n <= 1 || a == NULL) {
       if (n <= 0 || a == NULL) return INT_MIN;  // or throw error
       return a[0];
     }
     ...
   

2. 改变 int find_max(int *a, int n) --> int find_max(const int *a, int n)也允许传递常量数组。

3. 数组大小最好输入为 size_t而不是 int .

   int find_max(const int *a, size_t n) {
     ...
   }