Java中的递归 它是如何工作的？[重复]

Question

请在下面的代码中解释递归语句的工作原理。

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，其值为 6，则变为 30。那么这30个人会去哪里呢？

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

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

如果我放置另一个语句，在方法每次以这种方式调用自身时检查变量< code>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从何而来？我想我已经严重地陷入了代码的工作中。

Answer 1

在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），然后等待它完成，因为结果取决于它。

但是，事实上R（5），你也做了一个递归调用，你必须等待。

依此类推，直到我们达到极限 factR（1），它将只返回 1。

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

Answer 2

这里您可能忽略了< code>n是函数的局部变量。这意味着对你的函数的每一次调用(无论是否通过递归)都会得到一个新的变量< code>n，其中包含该函数的参数。因为它是值类型，所以它是复制的，而不是对原始值的引用。因此，在一个调用中对它的任何更改都不会影响其他(递归)调用中的变量。

结果，您的函数首先获得6的副本，并将其减少为1作为函数下一次调用的副本。该调用获得6-1=5的“副本”并再次减少它-依此类推。当它到达1时，它还返回1。然后它在调用堆栈中再次向上工作，并将最后一次调用的结果与此调用中的局部变量相乘。因此1与2相乘并返回。该结果与3相乘，依此类推。最后你得到阶乘。

Answer 3

该函数一直扩展到终止语句(< code>n == 1)。所以假设< code>n = 6，那么我们有< code > factR(n-1)* n = factR(5)* 6 ，但是什么是< code>factR(5)？它只是< code>factR(4) * 5，所以我们看到< code > factR(5)* 6 =(factR(4)* 5)* 6 。现在注意< code>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