Without using a loop, I'm trying to count the number of times a given integer is in an array using recursion. I keep getting a StackOverflow error and I can't figure out why.
public static int countOccurrences(int[] arr, int n) {
if (arr.length == 0) {
return 0;
}
if (arr[0] == n) {
return 1 + countOccurrences(arr, n - 1);
}
return countOccurrences(arr, n - 1);
}
}
If you can use only two parameters, then try:
public static int countOccurrences(int[] arr, int n) {
if (arr.length == 0) {
return 0;
}
if (arr[0] == n) {
return 1 + countOccurrences(Arrays.copyOfRange(arr, 1, arr.length), n);
}
return countOccurrences(Arrays.copyOfRange(arr, 1, arr.length), n);
}
the problem with above code is that the base condition will never be satisfied as you are never trying to reduce the length of the array. To keep track of length traversed, you can use a variable that starts from end to start ( or from start to end your choice ) . And let's say , num is the value that you want to count. Then you can change your code to like this :
public class CountFrequency {
public static void main(String[] args) {
int A[] = { 1, 2, 3, 4, 5, 5 };
int count = countOccurences(A, 5);
System.out.println(count);
}
private static int countOccurences(int[] arr, int num) {
return helper(arr, num, arr.length - 1);
}
private static int helper(int[] arr, int num, int i) {
if (i == -1) {
return 0;
}
if (arr[i] == num)
return 1 + helper(arr, num, i - 1);
else
return helper(arr, num, i - 1);
}
}
and the output is
2
i==0 should be i==-1. You want to include the element at index 0.