Thread: Recursive_java_function

Hello,

I've written the following code to find out the number of occurrences of a number in a sorted array (example: [ 1 3 3 4 8] for 3, it prints 2 occurrences).

The problem is that I'm using a recursive function, and the only solution I've found was to declare the counter as a global variable (public static int contor =0.

I want to declare the counter INSIDE the recursive function countOccurrences. How do I do that without losing counter values?

Thanks in advance. My code is below:

 
 
public class teste_Iulia {
 
	public static int contor =0; 
 
	public static void main(String []args){
 
		int v[]={1, 2, 4, 4, 10, 10, 20 };
		int key = 4;
 
		int contor = countOccurrences(v, key, 1, 7);
 
		System.out.println(contor);
 
 
	}
 
 
 
	private static int countOccurrences(int[] v, int key, int lower, int upper) {
		// TODO
	    // Calculati recursiv numarul de aparitii ale lui key in v
	    // intre pozitiile lower si upper. 
	    // La calcularea pozitiei de mijloc folositi
	    //         int m = lower + (upper - lower) / 2;
	    // pentru a evita overflow la adunarea pe numere intregi.
 
 
		if(lower>=upper) return contor;
 
		else{
 
 
		int m = lower+(upper-lower)/2;
		System.out.println("m "+m);
 
		if(v[m]==key) {
			contor++;
		}
 
		if(v[m]>key)
			return countOccurrences(v, key, lower, m);
 
		else
			return countOccurrences(v, key, m+1, upper);
 
		}
 
 
	}
 
}

Originally Posted by radulescuiulia

...The problem is that ...the only solution I've found...

A bigger problem is that your function is bugous.

I mean, if your binary search just happens to land on the first of two occurrences and there are exactly two occurrences, well, OK, but. a few runs with different points of occurrence shows some incorrect counts:

for v = [8, 9, 10, 11, 12, 13, 14]:
countOccurrences(7) = 0 <---> OK!

for v = [7, 8, 9, 10, 11, 12, 13]:
countOccurrences(7) = 0 <---> Huh? Should be 1

for v = [1, 7, 9, 10, 11, 12, 13]:
countOccurrences(7) = 1 <---> OK!

for v = [1, 2, 7, 10, 11, 12, 13]:
countOccurrences(7) = 1 <---> OK!

for v = [1, 2, 3, 7, 11, 12, 13]:
countOccurrences(7) = 1 <---> OK!

for v = [1, 2, 3, 4, 7, 12, 13]:
countOccurrences(7) = 1 <---> OK!

for v = [1, 2, 3, 4, 6, 7, 13]:
countOccurrences(7) = 1 <---> OK!

for v = [1, 2, 3, 4, 5, 6, 7]:
countOccurrences(7) = 1 <---> OK!

for v = [7, 7, 9, 10, 11, 12, 13]:
countOccurrences(7) = 1 <---> Huh? Should be 2

for v = [1, 7, 7, 10, 11, 12, 13]:
countOccurrences(7) = 1 <---> Huh? Should be 2

for v = [1, 2, 7, 7, 11, 12, 13]:
countOccurrences(7) = 2 <---> OK!

for v = [1, 2, 3, 7, 7, 12, 13]:
countOccurrences(7) = 1 <---> Huh? Should be 2

for v = [1, 2, 3, 4, 7, 7, 13]:
countOccurrences(7) = 2 <---> OK!

for v = [1, 2, 3, 4, 6, 7, 7]:
countOccurrences(7) = 1 <---> Huh? Should be 2

for v = [7, 7, 7, 10, 11, 12, 13]:
countOccurrences(7) = 1 <---> Huh? Should be 3

for v = [1, 7, 7, 7, 11, 12, 13]:
countOccurrences(7) = 2 <---> Huh? Should be 3
.
.
.
// Etc.
.
.
.
// With a seven-element array:
// Your method can not get the correct count value for occurrences greater than two.
.
.
.


Cheers!

Z