Secondo me è l' approccio che è sbagliato.
Scegli un pivot ma il controllo avviene solo in un senso: dalla metà dell' array in poi.
E fai due chiamate ricorsive che potrebbero contare due volte gli stessi elementi.
Oltre al fatto che dopo le chiamate ricorsive conti ancora gli elementi.
Ti propongo un algoritmo migliore.
Questo è il prototipo:

codice:
int conta(int* v,int i, int j);
// chiamata nel main:
conta(v,0,N-1); // se l' array ha dimensione N
Algoritmo:

1)Se i<=j:
....Controllo v[i] e v[j], incrementando il risultato ad ogni valore che combacia con quello cercato;
2)Aggiungo al risultato conta(v,i+1,j-1);
3)Ritorno il risultato finale.

PS: Nel caso speciale in cui i==j, devi fare solo un controllo.