跟踪递归

Question

我正在学习递归，并且在追踪递归方面有困难。 这是我的问题，我有解决方案，它工作得很好。 我被卡住了一些点，无法继续跟踪。

问题： 给定一个int数组，是否有可能选择一组int，使得该组相加到给定的目标。

解决方案：

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

开始= 0（其中我们必须开始阵列）

NUMS [] = {10,8,6}目标= 16

请帮帮我跟踪问题？

Answer 1

开始通过编号线

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

这里的执行（假设这是你所要求的）：

1 call groupSum1(0, {10, 8, 6}, 16) 
    1. 0 < 3 next 
2 call groupSum1(1, {10, 8, 6}, 6) 
    1. 1 < 3 next 
3 call groupSum1(2, {10, 8, 6}, -2) 
    1. 2 < 3 next 
4 call groupSum1(3, {10, 8, 6}, -8) 
    1. 3 == 3 return false to call 3  
back to call 3 in line 2. 
5 call groupSum1(3, {10, 8, 6}, -2) 
    1. 3 == 3 return false to call 3 
back to call 3 in line 3. 
    return false to call 2 
back to call 2 in line 2. 
6 call groupSum1(2, {10, 8, 6}, 6) 
    2 < 3 next 
7 call groupSum1(3, {10, 8, 6}, 0) 
    3 == 3 return true to call 6 
back to call 6 in line 2. 
    return true to call 2 
back to call 2 in line 3. 
    return true to call 1 
back to call 1 in line 2. 
    return true 

在递归调用前面的数字只是一个指标我用来跟踪深度。我希望这是可以理解的。

Answer 2

将代码视为连续调用函数可能会有所帮助，直到它到达目标（或false）。 “最内层”呼叫的结果将返回true（或target == 0）。

有了，下面的条件会或不会被满足：

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