Problems with recursion in c

Question

I’m trying to learn recursion and I’m doubtful on a question I was doing in c, I need to add up how many numbers of a vector with n elements are larger than a number x. This recursion just doesn’t get into my head, I need a clear.

#include <stdio.h>
#include <stdlib.h>

int busca(int v[], int n, int k)
{
  int x = 0;
  if(n == 1)
  {
    if( k < v[0])
     x= x + 1;



    }


  else
  {  
    if(k <  v[n])
      x = x+ 1;
      busca( v, n-1 ,k);
    }



      return x;


}


int main()
{
  int n, k,x;



  printf("DIGITE A QUANTIDADE DE ELEMENTOS DO VETOR:");
  scanf("%d", &n);

  int v[n];
  int i;

  for(i = 1; i <= n; i++)
  {
    printf("Digite o elemento %d: ", i);
    scanf("%d", &v[i]);
  }

  printf("Digite um numero: ");
  scanf("%d", &k);


//printf ("%d",
printf("x = %d", busca(v, n, k));

  return 0;
}

Answer 1

The recursion you want to make boils down to the following logic:

• Check if the item you go to is larger than the k and account for 1 if or 0 otherwise
• Call the same function recursively for the next element by summing its result

Implementation:

int busca(int v[], int n, int k) {
    if (--n<0) return 0; //se chegou ao fim retorna 0

    return (v[n]>k?1:0) + busca(v, n, k);//contabilizar 0 ou 1 e somar com a próxima busca
}

The main is accessing the array outside valid positions:

for(i = 1; i <= n; i++)

Is going to 1 to n, but arrays start at 0. So it has to start at 0 and go up to n-1.

After this adjustment we get the main thus:

int main() {
    int n;
    printf("DIGITE A QUANTIDADE DE ELEMENTOS DO VETOR:");
    scanf("%d", &n);

    int v[n], i, k;    
    for(i = 0; i < n; i++) {
        printf("Digite o elemento %d: ", i);
        scanf("%d", &v[i]);
    }

    printf("Digite um numero: ");
    scanf("%d", &k);
    printf("x = %d", busca(v, n, k));

    return 0;
}

See the example in Ideone