Recursive function that returns the number of numbers greater then the first index of an array

caiomartins1

I've got a function that solves the problem but I'm not sure if it is the correct way to write the recursive function

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

the output of [3,5,1,6] should be 2

chux - Reinstate Monica

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

The code looks OK yet it breaks the spirit of using recursion.¹

Such code could readily be done with a simple loop instead of n recursive calls.

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

Could could halve the problem at each step. At least the would have only log2(n) recursion depth rather than n as in OP's code.

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);
}

Some compilers will detect OP's construct and perform tail end recursion optimization yet I see a simple loop a better approach.

Use recursion when it makes sense. Use a loop when possible.

Note: better to use size_t than int for array size and indexing. (not shown here)

¹ Code fails for n <= 0.
A better function signature would be size_t greaterThanFistIndex(const int *v, size_t n)

Collected from the Internet

Please contact [email protected] to delete if infringement.