了解递归如何使用多个返回

Question

下面的问题来自于CodingBat：给定一个数组，是否可以选择一组整数，使其与给定的目标相加？

站点作者提供了以下解决方案：

public boolean groupSum(int start, int[] nums, int target) {
  if (start >= nums.length) return (target == 0);
  if (groupSum(start + 1, nums, target - nums[start])) return true;
  if (groupSum(start + 1, nums, target)) return true;
  return false;
}

假设我想尝试下面的例子，其中nums=[2,4,8]并调用groupSum(0,nums,10）。

我看到groupsum(0,nums,10)将调用groupsum(1,nums,10)和groupsum(1,nums,8)。

Groupsum(1,nums,10)调用Groupsum(2,nums,10)和Groupsum(2,nums,6)

Groupsum(1,nums,8)调用Groupsum(2,nums,8)和Groupsum(1,nums,4)

等等。

在处理代码时,我看到了以下调用：

groupSum(3,nums,10)
groupSum(3,nums,2)
groupSum(3,nums,6)
groupSum(3,nums,-2)
groupSum(3,nums,8)
groupSum(3,nums,0)
groupSum(3,nums,4)
groupSum(3,nums,-4)

我看到groupsum(3,nums,0)应该返回true，因为第一行:
if(start>=nums.length)return(target==0)；，但我对其他调用感到困惑，如groupsum(3,nums,-4)。由于target！=0，从第一行开始，它应该清楚地导致false。

另外，有人能解释一下为什么return true语句在

if (groupSum(start + 1, nums, target - nums[start])) return true;

我以为第一行就能决定真假。

if (groupSum(start + 1, nums, target)) return true;

Answer 1

除了Kolink在Java的详细漫步之外，我还创造了这张照片来帮助我看到：

public class TestRecursion{

    public static boolean groupSum(int start, int[] nums, int target, String s) {
        System.out.println(new String(new char[start]).replace("\0", "    ")+"start="+start+" target="+target+" parent="+s);
        if (start >= nums.length) return (target == 0);
        if (groupSum(start + 1, nums, target - nums[start], "A:"+start+"_"+target)) return true;
        if (groupSum(start + 1, nums, target, "B:"+start+"_"+target)) return true;
        return false;
    }

    public static void main(String... args){
        int[] nums = {2,4,8};
        groupSum(0, nums, 10, "");
    }
}

输出：

start=0 target=10 parent=
    start=1 target=8 parent=A:0_10
        start=2 target=4 parent=A:1_8
            start=3 target=-4 parent=A:2_4
            start=3 target=4 parent=B:2_4
        start=2 target=8 parent=B:1_8
            start=3 target=0 parent=A:2_8

Answer 2

基本上功能可以分解为：

>

如果“start”（数字数组中的当前位置）是数组末尾的一部分（换句话说，如果我们已经尝试了所有的数字），则如果达到目标（即为零），则函数成功

否则，继续使用包含的当前数字(target-nums[start])迭代(start+1)，如果有效，则返回true

否则，包含当前数字不起作用，所以继续迭代而不包含当前数字。如果有效，则返回true

如果我们已经做到了这一点，那么就没有办法添加起作用的数字，所以返回false。

您已经分解了所有可能的函数调用的步骤，正如您所观察到的，有一个返回true（其中target为零）。这个true结果级联将递归备份为最终返回值。

以下是其工作原理的粗略分类：

groupSum(0,[2,4,8],10)
0 >= 3? no, so continue:
groupSum(1,[2,4,8],10-2)?
  1 >= 3? no, so continue:
  groupSum(2,[2,4,8],8-4)?
    2 >= 3? no, so continue:
    groupSum(3,[2,4,8],4-8)?
      3 >= 3? yes. -4 == 0? no, return false
    groupSum(3,[2,4,8],4)?
      3 >= 3? yes. 4 == 0? no, return false
    return false
  groupSum(2,[2,4,8],8)?
    2 >= 3? no, so continue:
    groupSum(3,[2,4,8],8-8)?
      3 >= 3? yes. 0 == 0? yes, return true
    yes, return true
  yes, return true
yes, return true

希望这有帮助！