java - 使用 '|' 或 '||' 运算符的递归在基本情况下不返回 false

Question

所以我正在研究用来解决代码挑战的递归方法。我相信这可能只是我的一个误会。这是递归函数。

    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]);
    }

现在它的工作原理是，如果我的数组中的整数以任何组合给出我正在寻找的最大值，它最终会给我 true 或 false，否则它将返回 false。我不明白的是，如果我 System.out.println(Arrays.toString(arr) 我可以看到我的数组被减少到 0 长度，如果我调试它似乎会命中该行 if(arr.length == 0) return false;。那么为什么该函数不会在那里中断并返回 false。这个递归函数本质上继续运行。这是我在这个用例中看到的控制台数组

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

输出:

[-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

我理解 Arrays.copyOfRange 如何不断删除数组的索引，但我想我不理解运算符 | (我认为 || 也有效)以及为什么我需要 max=arr[0]。基于调试，看起来 canSum(Arrays.copyOfRange(arr, 1, arr.length), max-arr[0]) 在我的 arr.length = 0 时运行。OR 真的是这样吗就像这里的三元递归函数调用一样？我不确定如何 'return recurseFunct(n-1, m) | recurseFunct (n-1, m-n[0])' 正是在这种情况下工作。它看起来真的很方便，我想更好地理解它。

***** 添加此视频，因为它支持已接受的答案********

您可以在调试器的左侧直观地看到在此递归中使用的堆栈。堆栈的大小会略有变化，直到最终完全清空。一旦为空，我将在此时的递归函数中返回 true 或 false。这对我来说是一次很好的学习经历。谢谢你!

Answer 1

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.

函数调用顺序如下。 (括号中的索引)。

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

函数调用将存储在如下所示的堆栈中

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

如果 call(2) 返回 false，它将从堆栈中弹出 call(2)，然后返回到 call(1)，并将 call(3) 压入堆栈。

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

如果call(3)返回false，则会从栈中弹出call(3)，返回call(1)，call(1)将返回(call(2) || call(3))，弹出call (1)从栈中返回call(0)并压入call(4)。

因此，即使任何函数调用返回 false，仍有剩余的一堆调用需要执行，因此

recursive function keeps going essentially