What is causing this StackOverflowError?

Question

What am I missing? I have my base case and it appears that the 'left side' runs with no problem, but I get the error when the right side gets executed. I'm fairly new to recursion and I'm sure the answer is pretty obvious, but I can't seem to find it.

Basically, I have a list that I'm trying to see how many subsets are in that list that, when added, equal the constant D. I'm using an ArrayList with true and false values to create a decision tree, then using that list to find the sums using "test", a global ArrayList.

public void recSubSetSum(ArrayList<Boolean> subSetList){

    if(calcSumOfList(subSetList) == D)
        subsetsFound++;

    else if(calcSumOfList(subSetList) < D){
        for (int i = 0; i < test.size(); i++) {
            ArrayList leftList = new ArrayList<>();
            copyList(leftList, subSetList);

            leftList.add(true);
            if(calcSumOfList(leftList) < D)
                recSubSetSum(leftList);


            ArrayList rightList = new ArrayList<>();
            copyList(rightList, subSetList);

            rightList.add(false);
            if(calcSumOfList(rightList) < D)
                recSubSetSum(rightList); //this is where the error occurs 

        }//for

    }//else

    else{
        subsetsNotFound++;
    }
}


    public int calcSumOfList(ArrayList<Boolean> boolList){
    int sum = 0;
    int j =0; //I used j because it was giving me a outOfBoundsException when I uses i
    for (int i = 0; i < boolList.size(); i++) {
        if(boolList.get(i) == true){
            sum+= test.get(j);

            j++;
        }

    }//for
    return sum;
}//calc sum of list

Thanks in advance!

Answer 1

This is because the if statement before the error line is incorrect:

if(calcSumOfList(rightList) < D)
       recSubSetSum(rightList); //this is where the error occurs 

The condition is already satisfied by the outer if statement:

else if(calcSumOfList(subSetList) < D){

This is because you are copying the contents of subSetList into rightList and the calcSumOfList does not add to the value of the list if an entry is false, making rightList the same value as the original subSetList. So the method recurses every time, causing a StackOverflow.

Answer 2

Because recursing down the right never increases the sum of the subset, your recursion can go on forever. If you keep adding false to your array, you will always hit the < D case, and you will always execute the code that recurses over rightList.

calcSumOfList never throws an exception even though rightList is larger than the actual list you're looking at because it never has to access test, since boolList.get(i) will always return false (since your rightList is filled with nothing but false values).

You need to add a base case for when subSetList is the same size as test, and can no longer be added to.