java - 一种方法Java中的双重递归

Question

我很确定我完全理解只有一个递归的方法是如何工作的。

例如)计算阶乘

public int factorial(int n){  //factorial recursion
    if(n==0){
        return 1;
    }
    else{
        return n*factorial(n-1);
    }
} 

对于这些方法，我什至可以描绘堆栈中发生的事情以及在每个堆栈级别返回的值。

但是每当我遇到带有双重递归的方法时，噩梦就开始了。

下面是一个来自coding bat的双重递归的递归问题。

Ex) 给定一个整数数组，是否可以选择一组整数，使得该组总和等于给定的目标？如果是，则为真。如果不是，则为假。 您使用 3 个参数；起始索引start，一个int数组nums，目标int值target。

下面是这个问题的解决方案。

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

我对这个解决方案的理解是这样的。假设我得到了一个数组 {2,4,8}，起始索引 = 0，目标值为 10。所以 (0,{2,4,8},10) 通过该方法进入, 该函数在

处被重新调用

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

所以它变成了 (1,{2,4,8},8) 并且它一遍又一遍直到开始索引命中
3。当它达到 3 时。最后一层(？)的堆栈进入第二次递归调用。这就是我开始忘记正在发生的事情的地方。

有人能帮我分解一下吗？当人们使用双重递归时，(我知道它非常低效，在实践中，几乎没有人因为它的低效而使用它。但只是为了理解它。)他们真的可以想象将要发生的事情吗？或者他们只是希望基本情况和递归能够正常工作而使用它？我认为这通常适用于所有编写合并排序、汉诺塔算法等的人。

非常感谢任何帮助..

Answer 1

双重递归的思想是将问题分解为两个较小的问题。解决较小的问题后，您可以加入他们的解决方案(如在合并排序中所做的那样)或选择其中一个 - 这在您的示例中完成，如果解决第一个较小的问题，则只需要解决第二个较小的问题没有解决全部问题。

您的示例尝试确定是否存在输入 nums 数组的子集，其总和为 target 总和。 start 确定当前递归调用考虑数组的哪一部分(当它为 0 时，考虑整个数组)。

问题分为两个，因为如果存在这样的子集，它要么包含数组的第一个元素(在这种情况下，问题就简化为查找是否存在数组的最后 n-1 个元素的子集)总和为 target 减去第一个元素的值的数组)或不包含它(在这种情况下，问题简化为查找是否存在最后 ​​n-1 个元素的子集总和为 target 的数组)。

第一个递归处理子集包含第一个元素的情况，这就是为什么它进行递归调用以查找目标总和减去数组剩余 n-1 个元素中的第一个元素的原因。如果第一次递归返回 true，则意味着所需的子集存在，因此永远不会调用第二次递归。

第二次递归处理子集不包含第一个元素的情况，这就是为什么它会进行递归调用，在数组的剩余 n-1 个元素中查找目标总和(这次是第一个元素不会从目标总和中减去，因为第一个元素不包含在总和中)。同样，如果第二次递归调用返回 true，则表示所需的子集存在。