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

I'm not sure if it is the correct way to write the recursive function

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

这样的代码可以很容易地用一个简单的循环而不是 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) 递归深度而不是 n就像在 OP 的代码中一样。

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)