java - Java中的递归如何工作？ [复制]

This question already has answers here:

Understanding how recursive functions work

(18个回答)


5年前关闭。




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

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转到哪里呢？

然后该方法将自行调用，这次n-1变为4，然后与n相乘，如果IFt的值为“6”，则n-1乘以4 * 6 = 24，我认为这是错误的。因为如果我们经过这种方式，那么在下一个通话中
该过程将类似于:n-1将变为3 * n，如果IF保持相同的值，即6，则它将变为3 * 6 =18。然后，如果我们乘以并假设n保持值6，则下一个调用发生，并且n-1变为2然后2 * 6 = 12，最后调用n-1 = 1 * n =6。我的意思是，很明显n-1将减小n的值，即6-1 = 5，然后5-1 = 4，然后4-1 = 3，则3-1 = 2和2-1 = 1。但是问题是，每次方法调用自身时，将乘以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如何确定将结果值放回到result变量中？

如果每次方法以这种方式调用自身时，我都放置另一条语句来检查变量ojit_code的值是什么，如下所示:

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的来源是什么？我认为我严重地陷入了代码的工作之中。

最佳答案

该函数将扩展，直到到达终止语句(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