Java中一个方法中的双重递归

Question

Java中一个方法中的双重递归

3

我很确定我彻底理解了只有一次递归的方法是如何工作的。例如：计算阶乘。

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

对于这些方法，我甚至可以想象出堆栈中发生的情况以及每个堆栈级别返回的值。

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

下面是来自Coding Bat的一个具有双重递归的递归问题：

例如，给定一个int数组，是否可以选择其中一组int，使其总和等于给定目标？如果是，则为true。如果不是，则为false。您使用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时，最后一层的堆栈进入第二次递归调用。这是我开始迷失发生了什么的地方。

有人能为我解释一下吗？当人们使用双重递归时，他们能够真正可视化会发生什么吗？还是他们只是希望基本情况和递归能够正常工作？我认为这适用于所有编写归并排序、汉诺塔算法等的人们。

非常感谢任何帮助。

- Hello

4

你在这里创造术语。它不是“双递归”——你展示的只是普通递归。同时，就像一位明智的人曾经说过，“要理解递归，你必须先理解递归”。 - user719662

好吧，我猜我还没有理解递归。所以请给我一些启示。 - Hello

1

毫不客气：https://dev59.com/tHVD5IYBdhLWcg3wXaYd https://en.wikipedia.org/wiki/Recursion https://dev59.com/ZXVC5IYBdhLWcg3w-mZO - user719662

这不是“双重”递归，因为在groupSum()内部对groupSum()的第二次调用并没有使堆栈变得两倍深。 - NickJ

抱歉用词不当，我本以为应该使用“double”，因为它使用了两次递归。 - Hello

3个回答

2

如果你想可视化它，通常就像一棵树。首先沿着树的一个路径走到底，然后往回走一步并选择另一条路径（如果可能）。如果没有或者你对结果感到满意，就再往回走一步，以此类推。

我不知道这是否能帮到你，但当我学习递归时，把我的方法看作已经起作用是有帮助的。所以我想：太好了，基本上我的方法已经起作用了，但我不能使用相同的参数调用它，必须确保我使用不同的参数返回正确的值。

如果我们以这个例子为例：首先我们知道，如果我们没有剩余数字可以查看，那么答案取决于目标是否为0。（第一行）

现在我们要怎么做呢？哦...我们需要花些时间考虑一下。只需考虑第一个数字。什么情况下它是解的一部分呢？嗯，那就是如果你可以使用其余的数字创建 target - firstnumber。因为在这种情况下，当你加上 firstnumber 时，就达到了目标。所以你尝试看看是否可能。如果是，就可以解决问题。（第二行）

但如果不行，第一个数字仅仅是解决方案中不重要的一部分。所以你需要再试一次，不使用该数字来构建目标。（第三行）

这基本上就是全部内容。

当然，要想这样思考，你需要两个条件： 1. 你需要相信你的方法已经适用于其他参数。 2. 你需要确保你的递归终止。这个例子中的第一行就是如此，但你应该始终思考是否存在任何参数组合将创建无限递归。

- Mark

1

尝试这样理解：递归可以重写为while循环，其中while的条件是递归停止条件的否定。正如已经提到的，不存在所谓的双重递归。

- adranale

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eran · Accepted Answer

双重递归的想法是将问题分解为两个较小的问题。一旦解决了这些较小的问题，您可以将它们的解决方案合并在一起（就像归并排序中所做的那样），或者选择其中一个 - 这在您的示例中完成，如果解决第一个较小的问题未能解决完整问题，则只需要解决第二个较小的问题。

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

该问题被分为两个部分，因为如果存在这样的子集，则它要么包含数组的第一个元素（在这种情况下，问题被减少为查找是否存在数组的最后n-1个元素的子集，其总和为目标减去第一个元素的值），要么不包含它（在这种情况下，问题被减少为查找是否存在数组的最后n-1个元素的子集，其总和为目标）。

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

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