### Counting the occurrence of an element within an array using recursion

Define a function int occurrences(int A[], int size, int key) that counts the number of times a key value occurs in an array. Write one version of this function using iteration and another using recursion.

I have already done the iterative part; i am attempted to solve the recursive part of this problem...I haven't been able to figure out a way to make it work but this is what I have:

const int size = 7;

int rOccurences(int A[], int size, int key){ //count occurrences of key

int keyCount = 0;

if (size == 0) //key does not occur in array
return keyCount = 0;

else
return keyCount = 1 + rOccurrences(A, size - 1, int key);
}

I realize after trying this it returns 7, I know why. I am just having trouble thinking about this recursively. If someone could point me in the right direction that would be awesome. This is a review question, it is not a graded assignment. However, help would still be greatly appreciated.
Last edited on
well, think recursively:

the number of times key occurs in A is the number of times key occurs in A[0] (which is zero or one) plus the number of times key occurs in the rest of A:

 ``12345`` ``````if (A[0] == key) keyCount = 1; else keycount = 0; return keyCount + rOccurences(A+1, size-1, key);``````

or, alternatively, it is the number of times key occurs in the last element of A, that is, A[size-1], plus the number of times key occurs in the rest of A:

 ``12345`` ``````if (A[size-1] == key) keyCount = 1; else keycount = 0; return keyCount + rOccurences(A, size-1, key);``````

Or, shorter and adding the terminating condition,

 ``1234567`` ``````unsigned int rOccurrences(const int A[], unsigned int size, int key) { if(size) return (A[0] == key) + rOccurrences(A+1, size-1, key); else return 0; }``````

Last edited on
Thank you so much for your help!
Topic archived. No new replies allowed.