CODEWITHSUNDEEP
javaalgorithmrecursionbitwise-operators
Puerto
Puerto

Reputation: 1134

Recursion with '|' or '||' operator not returning false in base case

So I'm looking at recursion method I'm using to solve code challenge. I believe this might be just a misunderstanding on my part. Here is the recursive function.

    public static boolean canSum(int[] arr, int max)
    {
        System.out.println(Arrays.toString(arr));
        if(max == 0) return true;
        if(arr.length == 0) return false;
        else return canSum(Arrays.copyOfRange(arr, 1, arr.length), max) | canSum(Arrays.copyOfRange(arr, 1, arr.length), max-arr[0]);
    }

Now it works in that it will eventually give me true or false if the integers in my Array in any combination will give me the max value I'm looking for, or it will return false. What I don't understand is if I System.out.println(Arrays.toString(arr) I can see my array being reduced to 0 length and if I debug it appears to hit the line if(arr.length == 0) return false;. So why does the function not break there and return false. This recursive function keeps going essentially. Here is the console arrays I'm seeing for this use case

System.out.println(canSum(new int[]{3,5,-1,8}, 12));

Output:

[-1, 3, 5, 8]
[3, 5, 8]
[5, 8]
[8]
[]
[]
[8]
[]
[]
[5, 8]
[8]
[]
[]
[8]
[]
[]
[3, 5, 8]
[5, 8]
[8]
[]
[]
[8]
[]
[]
[5, 8]
[8]
[]
[]
[8]
[]
[]
true

I understand how the Arrays.copyOfRange keeps removing an index of the array but I guess I'm not understanding the operator | (I think || works as well) and why I need to max=arr[0]. Based on debug, it looks like canSum(Arrays.copyOfRange(arr, 1, arr.length), max-arr[0]) runs when my arr.length = 0. So is the OR really like ternary here for recursive function call? I'm not sure how 'return recurseFunct(n-1, m) | recurseFunct (n-1, m-n[0])' works in this scenario exactly. It seems really handy and I would like to understand it better.

****** Adding this video as it supports the accepted answer *******

You can visually see the stack that is being used in this recurse on the left hand side of the debugger. The size of the stack varies for a bit until it finally empties completely. Once empty i will return true or false in the recursive function at that point. This was good learning experience for me. Thank you!

enter image description here

Upvotes: 0

Views: 320

Answers (1)

Katha patel
Katha patel

Reputation: 131

If I debug it appears to hit the line if(arr.length == 0) return false;. So why does the function not break there and return false. This recursive function keeps going essentially.

The sequence of the function call is like below. (index in a bracket).

                 call(0)
                /       \
        call(1)     ||     call(4)
        /     \             /    \
    call(2) || call(3)  call(5) || call(6)  
    /\          /\      /\          /\
   /  \        /  \    /  \        /  \

The functions call will be stored in a stack like below

call(2)
call(1)
call(0)

if call(2) returns false, it will pop call(2) from the stack and come back to call(1) and push call(3) to stack.

call(3)
call(1)
call(0)

if call(3) returns false, it will pop call(3) from stack, come back to call(1), call(1) will return (call(2) || call(3)),pop call(1) from stack, come back to call(0) and push call(4).

so even if any function call returns false, there are a remaining bunch of calls to be performed and so

recursive function keeps going essentially

Upvotes: 3

Related Questions