C语言 递归函数，返回大于数组第一个索引的数字数

Question

递归函数，返回大于数组第一个索引的数字数

我有一个解决问题的函数，但我不确定这是否是编写递归函数的正确方法

int greaterThanFistIndex(int *v,int n){
    int a;
    if(n == 1){
        return 0;
    }else{
        a = greaterThanFistIndex(v,n-1);
        if(v[0] < v[n-1]){
            a++;
        }
    }
    return a;
}

[3,5,1,6] 的输出应为 2

Answer 1

我不确定这是否是编写递归函数的正确方法

代码看起来不错，但它打破了使用递归的精神。¹

这样的代码可以很容易地通过一个简单的循环来完成，而不是n递归调用。

int greaterThanFistIndex_iterate(const int *v,int n){
  count = 0;
  for (int i = 1; i<n; i++) {
    if (v[i] > v[0]) count++;
  }
  return count;
}

---

可以在每一步将问题减半。 至少只有log2(n(递归深度，而不是像OP代码那样n。

static int greaterThanFistIndex_r_helper(const int *v,int n, int first){
  if (n <= 0) {
    if (n == 0) return 0;
    return *v > first;
  }
  int first_half = n/2; 
  int second_half = n - first_half; 
  return greaterThanFistIndex_r_helper(v, first_half, first) +  
      greaterThanFistIndex_r_helper(v + first_half, second_half, first);
}
int greaterThanFistIndex_r(const int *v,int n){
  if (n <= 0) return 0;
  return greaterThanFistIndex_r_helper(v+1, n, *v);
}

一些编译器会检测 OP 的构造并执行尾端递归优化，但我看到一个简单的循环是更好的方法。

---

在有意义时使用递归。 尽可能使用循环。

注意：对于数组大小和索引，最好使用 size_t 而不是int。(此处未显示(

---

¹代码失败 n <= 0 。
更好的函数签名是size_t greaterThanFistIndex(const int *v, size_t n)