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

Question

以下问题来自codingbat:给定一组int,是否可以选择一组int中的一组,以便该组与给定目标相加？

该网站的作者提供了以下解决方案:

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.

也有人可以解释为什么返回真实陈述是必要的

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

我认为第一行将决定是真还是假.

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

Answer 1

基本上该功能可以细分为:

1. 如果"开始"(数字数组中的当前位置)是数组末尾的一部分(换句话说,如果我们已经尝试了所有数字),那么如果达到目标,则函数成功(即.零)

2. 否则,继续start+1使用当前数字included(target-nums[start])迭代(),如果有效则返回true

3. 否则,包括当前数字不起作用,因此继续迭代而不使用当前数字.如果有效,请返回true

4. 如果我们已经达到这一点,那么就无法添加有效的数字,所以返回false.

您已经分解了所有可能的函数调用的步骤,并且您观察到有一个返回true(目标为零的那个).此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

希望这可以帮助!