Java recursion class variable value is reset to 0

Question

I was trying to implement the coin change problem using recursion. I have written the following code and am facing a problem with the static class variable. 'answer' is a class variable and i am trying to add the return value to it in the loop. This works fine within the while loop but after the while loop ends the answer is reset to 0;

    while (i * currentCoin <= sum) {
    System.out.println("inside while; answer is " + answer);
          answer = answer
            + findCombinations(
                    sum - i * currentCoin,
                    new ArrayList<Integer>(denominations.subList(1,
                            denominations.size())));
    i++;

}

Below is all the code that I have written. You can copy and run it to check.

    import java.util.ArrayList;
    import java.util.Collections;

    public class CoinChangeHashMap {
static int answer = 0;

public static void main(String[] args) {

    int[] array = new int[] { 7, 3, 2 };
    ArrayList<Integer> input = new ArrayList<Integer>();
    getList(array, input);
    findCombinations(12, input);
    System.out.println(answer);
}

private static void getList(int[] array, ArrayList<Integer> input) {

    for (int i : array) {
        input.add(i);
    }

}

public static int findCombinations(int sum, ArrayList<Integer> denominations) {

    if (denominations.size() == 1) {
        if (sum % denominations.get(0) == 0) {
            return 1;
        }
        return 0;

    }
    int i = 0;
    int currentCoin = denominations.get(0);

    while (i * currentCoin <= sum) {
        System.out.println("inside while; answer is " + answer);

        answer = answer
                + findCombinations(
                        sum - i * currentCoin,
                        new ArrayList<Integer>(denominations.subList(1,
                                denominations.size())));
        i++;

    }
    return 0;
}}

**The output that I get is 0. but the expected output is 4. While debugging the output that I got is **

inside while; answer is 0
inside while; answer is 0
inside while; answer is 1
inside while; answer is 1
inside while; answer is 2
inside while; answer is 2
inside while; answer is 0
inside while; answer is 0
inside while; answer is 0
0

Any Help is appreciated.

Try printing the answer value after you have made the recursive call — Vishal, May 29 '16 at 03:09
that is not debugging, that is `System.out.println()`, debugging actually entails using the step debugger to step through the code one instruction at a time, not just printing stuff out willy nilly. — , May 29 '16 at 04:07
@JarrodRoberson, print statements are a tried and true method of debugging. Moreover, the print statements inserted into the code are helpful to demonstrate the problem to *us*. The question is about why the static variable's value is reset. That the OP might have discovered the answer for himself by running the code in a debugger does not make this a dupe. Nor does it even demonstrate lack of research. — John Bollinger, May 29 '16 at 04:12

score 0 · Accepted Answer · answered May 29 '16 at 04:03

The problem is related to your odd code structure, in which you convey the outcome of your recursive call sometimes by modifying static variable answer, and sometimes via the method's return value.

If you analyzed the problem more closely, you would discover that it is not upon exit from the loop that the partial results are lost, but rather some time after return from the method. Therefore, consider carefully the way you update the answer:

answer = answer + findCombinations( /* ... */ );

At the top-most level of your recursion, answer is initially 0. When Java evaluates the above expression, it evaluates first the left operand and then the right operand, then it adds them. That is, it evaluates answer, getting the result 0, before it performs the recursive call. The value of answer may be updated in the course of the recursive call, but those changes come too late. Only the bottom-most level of the recursion ever returns a value different from zero, so if the recursive call itself recurses at least one level deeper then it will return zero. In that case, the sum is computed as 0 + 0, and assigned to answer, clobbering any update the method performed.

You could resolve the problem by swapping the order of the operands in your sum, but it would be better, and not much harder, to get rid of the static variable altogether. Use a local variable within the method to accumulate results, and in all cases convey the total back to the caller via the method's return value.

Java recursion class variable value is reset to 0

1 Answers1