logo标签列表

Java中的递归，它是如何工作的？

javarecursion
6
请解释以下代码中递归语句的工作原理。
int factR(int n) {
    int result;

    if(n==1) return 1;

    result = factR(n-1) * n;
    return result;
}

我的理解是：

在上述语句中，factR(n-1)方法会一直调用自身，直到结束。假设我们想要得到6的阶乘，它将作为参数发送到此方法中。它将作为参数n接收，然后检查n的值；如果它为1，则返回1。但如果它不是1，例如我们的情况下是6，则递归语句将运行。

现在我面临的问题是，第一次n-1变成5并与n相乘，n保持值6，那么它变成30。那么这个30会去哪里呢？

然后该方法将调用自身，这次n-1变成4，然后乘以n，如果n保持值"6"，则4*6=24，我认为这是错误的。因为如果我们按照这种方式进行，那么在下一次调用中，过程将类似于，n-1将变为3*n，如果它保持相同的值即6，则它将变为3*6=18。然后发生下一个调用，n-1变为2，如果我们乘以n并假设n保持值6，则2*6=12，最后一次调用n-1= 1 * n = 6。我的观点是，显然n-1将减少值n-1即6-1=5，然后5-1=4，然后4-1=3，然后3-1=2，2-1=1。但问题是每次方法调用自身时将乘以哪个值的n？

如果你说当第一次乘法发生时，即"n-1"变成5时，乘以6=30，那么在下一次调用中5-1=4*30=120，然后4-1=3*120=360，然后3-1=2*360=720，最后1*720=720，那么Java如何确定将结果值放回到变量n中？

如果我再加上另一个语句来检查每次方法调用自身时变量result的值，就像这样：

int factR(int n) { 
    int result; 

    if(n==1) return 1; 

    result = factR(n-1)*n ;
    System.out.println(result);
    return result; 
}

然后我得到了这个输出：

2
6
24
120
720
Factorial of 6 is 720

我不明白它在第一次调用时如何产生2。这些值2、6、24、120和720从哪里来的？我认为我对代码的工作原理非常困惑。

4
你尝试过调试代码吗？ - TheLostMind
你的方法是错误的。在你的情况下，它不会首先得到 30。它将从 1*2 开始 -> 将结果传递给调用者方法 *3 -> 将结果传递给调用者方法 *4 等等。每次递归调用都会被放入堆栈中，当它到达不再进行任何递归的点时，堆栈会从顶部（最后一次调用）返回到底部（第一次调用）。 - SomeJavaGuy
2 不是第一个调用，它是第二个，只是你的第一个调用在 println 之前返回了。 - valepu
因为：1）在您的 System.out.println 之前有 if(n==1) return 1;，这意味着第一次调用不会被打印出来。 2）您的 System.out.println 在递归调用之后，这意味着首先递归将被调用，然后输出 ==> 输出将是“从后到前”。所以：第一个调用被跳过（1），第二个调用是1+2=2，第三个调用是123=6等。 - Arenim
如果(n==1) return 1; 是一个错误的条件：factR(0)会导致系统卡住。应该是 if(n <= 1) return 1; - Dmitry Bychenko
4个回答
7
函数会一直扩展，直到终止语句被执行（n == 1）。假设n = 6，那么我们有factR(n-1) * n = factR(5) * 6，但是factR(5)是什么呢？它只是factR(4) * 5，所以我们可以看到factR(5) * 6 = (factR(4) * 5) * 6。现在注意到factR(1) = 1，我们得到：
factR(6) = factR(5) * 6 
         = (factR(4) * 5) * 6 
         = ((factR(3) * 4) * 5) * 6 
         = (((factR(2) * 3) * 4) * 5) * 6 
         = ((((factR(1) * 2) * 3) * 4) * 5) * 6 
         = ((((1 * 2) * 3) * 4) * 5) * 6
         = (((2 * 3) * 4) * 5) * 6
         = ((6 * 4) * 5) * 6
         = (24 * 5) * 6
         = 120 * 6
         = 720
1
你可能忽略了的是，变量n是函数内部的局部变量。这意味着每次调用函数（无论是通过递归还是其他方式），都会得到一个新的变量n，其中包含该函数的参数。因为它是值类型，所以被复制而不是引用原始值。因此，在一个调用中对它进行的任何更改都不会影响其他（递归）调用中的变量。
因此，你的函数首先获得6的副本，并将其减1后作为副本提供给下一个函数调用。该调用获得“6-1=5”的“副本”，再次减少——以此类推。当它达到1时，它也返回1。然后它再次通过调用栈向上工作，并将上一次调用的结果与此调用中的局部变量相乘。因此，1乘以2并返回。该结果乘以3，以此类推。最终你得到了阶乘。
0
在Java中，我们有一个叫做堆栈的东西。
每次一个方法被另一个方法调用时，它就会被添加到堆栈中。
 ________
|factR(1)| = <prints nothing>
 ________
|factR(2)| = 2
 ________
|factR(3)| = 6
 ________
|factR(4)| = 24
 ________
|factR(5)| = 120
 ________
|factR(6)| = 720

这基本上意味着，为了完成factR(6)方法，必须先完成factR(5)，为了完成factR(5)，必须先完成factR(4)等等。

在factR(6)中，您调用factR(5)并等待其完成，因为结果取决于它。

但是，在factR(5)中，您也进行了递归调用，并且必须等待。

以此类推，直到达到限制factR(1)，它将返回1。

完成factR(1)后，factR(2)可以打印出结果并将结果返回给其父方法，以此类推，直到factR(6)打印出并返回其结果。

bruno_cw，阅读了Mukesh Kumar的上面的回答后，你的回答真的非常容易理解，坦率地说，它就像清晰的文字一样清晰明了 :-) ，我希望你能以这样美妙的方式分享知识，谢谢。 - Aurang Zeb Khan
哇，非常感谢！ :) - bruno_cw
-1

计算阶乘的方法应该像这样结构化，使用n：

int factorial(int n)
{
    if (n == 1)
        return 1;

    return n * factorial(n - 1);
}

在我看来，将新变量实例化在递归函数内部并不是一个很好的主意，因为由于作用域的原因，它们会在每次调用时被重置。
实际上，它与他的方法做的是一样的，只是代码更少，他能够通过打印语句来调试自己的代码。 - SomeJavaGuy
@KevinEsche 是的，我知道，但我个人认为实例化变量是不好的做法，因为由于递归，这些变量最终会超出范围，这会增加更多的混乱。 - m_callens
那并没有真正回答问题。 - bruno_cw
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接