algorithm - 用递归函数返回

Question

我很好奇 return 在使用递归函数时是如何工作的。例如，在下面的阶乘函数中，x 将在任何计算实际发生之前达到 1。

int factorial (int x){ 
    if (x==1){
        return 1;     
}else{
    return x * factorial(x - 1);
    }
}

假设 x = 3。按照逻辑，它似乎应该循环 3 次并返回 1:

• 3 != 1
• 否则:3 * 阶乘 (2)。
• 什么是阶乘 (2)？
• 回到顶部:2 != 1
• 否则:2 * 阶乘 (1)。
• 什么是阶乘 (1)？
• 返回顶部:1 == 1,
• 所以:返回 1。

但是，当然它实际上会返回 6。那么它究竟是如何工作的呢？

Answer 1

每次您说“那个递归调用的值(value)是多少？”，您就是在从上一次迭代中删除 x *。不这样做:

factorial(3)
3 * factorial(2)
3 * (2 * factorial(1))
3 * (2 * 1)
= 6

递归调用不像 goto 用新的参数再次到达函数的顶部。¹ 我们用新的参数再次调用函数，但只有那个调用有新参数值:调用者仍然拥有其参数和变量的旧值。

¹ 除非我们在谈论尾递归，我们不是，而且这只是一种优化。