algorithm - 使用递归函数返回

Question

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

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

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

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

score 1 · Accepted Answer

每次你说“那么递归调用的价值是什么？”，你就是x *从上一次迭代中删除了。如果不这样做：

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

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

¹除非我们谈论的是尾递归，否则我们不是，而且那只是一种优化。

score 1 · Accepted Answer

它不是返回顶部，而是在factorial函数内部调用factorial函数。

实际上，最后它返回 1，但它在行中将其作为结果返回

return x * factorial(x - 1);

之前对的调用factorial，wherex是 2。这又将 2 * 1 返回到对factorialwherex是 3 的先前调用。所以这给出了 3 * 2，将结果 - 6 - 返回到函数的第一次调用。

score 0 · Accepted Answer

递归函数调用与普通函数调用没有区别。return因此，一个呼叫的和另一个呼叫之间没有联系return。

在示例中，第一个return语句是

return 3 * factorial(2)

它将 3 乘以factorial参数为 2 的调用的返回值。

但是 factorial(2) 的返回值是

return 2 * factorial(1)

它将 2 乘以factorial参数为 1 的调用的返回值。

但是 factorial(1) 的返回值为 1。

Soreturn 2 * factorial(1)与相同return 2 * 1，即 2。

return 3 * factorial(2)与相同，return 3 * 2即 6。

score 0 · Accepted Answer

在第一步中，x = 3。然后你的函数返回3 * factorial(2)，它本身返回2 * factorial(1)（因为x仍然不等于 1），最后factorial(1)返回 1。

所以最后你得到了3 * 2 * 1 = 6。

score 0 · Accepted Answer

堆栈帧是在运行时用于存储有关函数调用的信息的记录，包括参数、局部变量、寄存器值和返回地址。对于每个连续的函数调用，我们将堆栈帧推入堆栈，并且当任何活动函数（位于堆栈顶部的函数）获得返回调用时，它的堆栈帧从堆栈中弹出并且它下面的函数被激活。这是示例。

在此处输入图像描述

因此，函数 factorial(3) 最后返回值 6。

5 回答 5