Alogrithm recursion codingbat

Question

Recursion-2 > groupSum6 http://codingbat.com/prob/p199368

I modified the solution from the first one example where the condition of using 6 is not present.

Below working solution:

public boolean groupSum6(int start, int[] nums, int target) {
  // Base case: if there are no numbers left, then there is a
        // solution only if target is 0.
        if (start >= nums.length) return (target == 0);

        // Key idea: nums[start] is chosen or it is not.
        // Deal with nums[start], letting recursion
        // deal with all the rest of the array.

        // Recursive call trying the case that nums[start] is chosen --
        // subtract it from target in the call.
        if (nums[start] == 6) 
            return groupSum6(start + 1, nums, target - nums[start]);
        if (groupSum6(start + 1, nums, target - nums[start]))
            return true;

        // Recursive call trying the case that nums[start] is not chosen.
        if (groupSum6(start + 1, nums, target)) return true;

        // If neither of the above worked, it's not possible.
        return false;
}

HOWEVER it is not working when I'd replace

if (nums[start] == 6) 
                return groupSum6(start + 1, nums, target - nums[start]);

with :

if (nums[start] == 6) 
                groupSum6(start + 1, nums, target - nums[start]);

//NOTE: missing return statement.

Then algo fails for arrays where the target is possible to get but without using 6. eg groupSum6(0, [5, 6, 2], 7) expected value false but returns true. takes 5+2, skipps 6, but as in description every 6 must be used.

My question is: how does the 'return' statement changes the flow of recursion

GBlodgett · Accepted Answer · 2018-06-28T13:39:03.693

Because java is pass by reference you aren't passing the actual object when you pass parameters to a method. You are passing a reference to the objects. So when you pass a reference to your objects, but take out the return call, the reference never gets resolved back to the variables, and you essentially throw away the results of your recursive call

Try this simple program to see what I mean:

public static int foo(int x) {
    x++;
    if(x < 10) {
        foo(x);
    }
    return x;
}

If we call System.out.println(foo(1)); this will print out 2, since the first x++ gets resolved, but you essentially throw away the results from all your recursive calls.

However if we change

if(x < 10) {
    foo(x);
}

To:

if(x < 10) {
    return foo(x);
}

The result will be 10 because we return the results from the recursive calls

Alogrithm recursion codingbat

1 Answers1