Рекурсивная функция, которая возвращает число чисел, превышающее первый индекс массива

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

Я не уверен, что это правильный способ написать рекурсивную функцию

Код выглядит OK , но он нарушает дух использования рекурсии. ¹

Такой код может быть легко выполнен с помощью простого цикла вместо 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)