Counting elements in array recursively - big arrays

Question

I am learning recursion and I am supposed to create a recursive method to count number of apperances of a specific number in an array, e.g.; {1,2,3,4,4,5} for number 4 should return 2. I know that recursion is not the ideal problem to solve this issue and I know that using endIndex is not ideal either, but that's just a textbook problem I can't seem to solve.

My method is not working well, since I always run out of heap when running through big arrays. How would I optimize such code? Thanks!

 public static int countNumber(int[] array, int startIndex, int endIndex, int 
   number) {
    int result = 0;
    if (startIndex==endIndex) {
        return result;
    }
    if (array[startIndex] == number ) {
        result++;
    }
    result = result + countNumber(array,startIndex+1,endIndex,number);
    return result;
   }

Forketyfork · Accepted Answer · 2019-02-22 23:28:26Z

5

Are you sure you run out of heap, not out of stack? Because running out of stack on a big array is something quite expected here. The depth of the recursion is always limited by the stack size.

You could split the array into two parts on each iteration and run the method recursively on both parts. That way, for n elements of the input array, the depth of recursion would be log2(n) instead of n. Something along the following lines:

if (startIndex == endIndex) {
    if (array[startIndex] == number) {
        return 1;
    }
    return 0;
}
return countNumber(array, startIndex, (startIndex + endIndex) / 2, number)
        + countNumber(array, (startIndex + endIndex) / 2 + 1, endIndex, number);

Of course, you could also just increase stack size (e.g. with -Xss10m parameter), or simply limit the size of your input array.

edited Feb 22, 2019 at 23:28

answered Feb 22, 2019 at 23:06

Forketyfork

7,8382 gold badges29 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user11104002 Over a year ago

Hey, your code throws array index out of bounds exception.

Forketyfork Over a year ago

Yes, sorry, fixed.

Collectives™ on Stack Overflow

Counting elements in array recursively - big arrays

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related