在Factorial中，return是如何工作的呢？

Question

我从最基础的东西开始思考递归，因为我过去一直在苦苦挣扎。我正在考虑这个阶乘解决方案：

int Factorial(int n)
{
    if (n == 0)
    {
        return 1;
    }
    return n * Factorial(n - 1);
}

所以这个函数会一直调用它自己，直到n == 0。然后，它继续在每次调用时返回值。这就是我不明白的地方:当它从基本条件返回时，它返回一个值，并且不断地从每个调用中加值。

这些值存储在哪里，以便最终能够返回总和？

Answer 1

正如您正确解释的那样，除非参数为0，否则函数Factorial将调用自身。由于它使用n - 1调用自身，因此递归调用序列最终将在n步骤之后停止。每次调用都是一个新的实例或函数的调用，计算都会暂停，直到新的实例返回。给定实例的状态保存在内存中称为堆栈的区域(在大多数当前环境中)。

当使用值0调用的最终实例返回时，最后一个调用实例可以完成其计算并将1 * 1返回给其调用者，依此类推，直到初始实例完成其乘法并返回其参数的阶乘。

-除非您对实现细节感兴趣，否则请停止阅读

上面代码的第一个问题是，如果n为负或非常大，程序可能会因为太多的递归调用而调用未定义的行为，每次调用都会消耗一些堆栈空间和有限的资源。

第二个问题：int类型的可能值范围有限。在大多数当前的系统中，int存储为32位。阶乘增长非常快，因此Factorial(12)产生479001600，这在乘以13时会导致算术溢出，因为结果6227020800不适合32位。算术溢出调用未定义的行为。

您可以尝试在这个站点上编译您的Factorial函数：http://gcc.godbolt.org/#。它有一个交互式编译器，并显示汇编代码。尝试不同的优化器选项：

• -m32 -O1将给出一个递归版本，不太难understand
• -m32 -O2表明编译器足够精明，可以将递归C实现转换为迭代汇编版本，比version.
• -m32 -O3更短更快。-O1产生的代码要复杂得多，涉及MMX寄存器上的-O1指令...可能比-O2版本更快，但完全是过度设计的，因为一个简单的小查找表不需要一次测试就足够了：

整数阶乘(整数n) {静态整数f3216 ={ 1，1，2，6，24,40320,362880,3628800,39916800,479001600，0，0，0 }；return f32n & 15；}

请注意，如何利用未定义的行为语义(任何东西都可以)来简化实现并删除测试。编译器是被允许这样做的，其中一些确实是这样做的。

Answer 2

要递归地计算给定输入的结果，递归函数使用不同的(以某种方式“较小”的)输入调用(其副本)自身，并使用此调用的结果构造其结果。除非到达基本情况，否则递归调用也会执行相同的操作。因此，调用堆栈就会在这个过程中发展。例如，为了计算Factorial(3)，它依次递归调用Factorial(2)、Factorial( 1 )、Factorial(0) (“缠绕”堆栈)，此时递归以Factorial(0) =1终止，然后堆栈以相反的顺序展开，并在沿调用堆栈返回到初始调用帧Factorial(3)的过程中计算结果，其中最终结果计算为3*2 =：6并最终返回。在此示例中，函数返回单个值。