在阶乘中，return是如何工作的？

Question

我正从最基本的方面着手研究递归，因为我在过去很挣扎。我在看这个阶乘解：

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

因此函数会一直调用自己，直到＜code＞n==0＜/code＞为止。然后在每次调用时返回值。这就是我不明白的：当它从基本条件返回时，它返回一个值，并不断添加每个调用的值。

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

Answer 1

所有内容都存储在堆栈中相应的激活记录¹中。

您的函数int Factorial（int n）；正在使用递归。第一个返回称为基本情况，它充当终止条件，第二个返回是递归步骤，这会导致调用同一个函数，其中一个参数（在基本情况if条件语句中使用）被修改。结果在达到基本条件后累积并返回。

这里有一个很好的递归解释，使用完全阶乘作为示例。

^{1.在计算机体系结构级别，结果存储在特定的寄存器中，累积最终结果。}

Answer 2

为了在给定的输入上递归计算其结果，递归函数使用不同的（以某种方式“较小”）输入调用（副本）自身，并使用此调用的结果来构造其结果。递归调用执行相同的操作，除非已达到基本情况。因此，调用堆栈在此过程中发展。例如，为了计算阶乘（3），这依次递归调用Factorial（2），Factorial（1），Factorial（0）（“清盘”堆栈），此时递归终止为Factorial（0） = 1，然后堆栈以相反的顺序展开，结果在沿着调用堆栈返回初始调用帧Factorial（3）的途中计算， 其中，最终结果计算为 3*2 =： 6，最后返回。在此示例中，函数返回单个值。

Answer 3

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

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

-------停止阅读此处，除非您对实现细节感兴趣--------

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

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

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

>

-m32-O1将给出一个递归版本，不太难理解。

-m32-O2表明，编译器足够精明，可以将递归C实现转换为迭代汇编版本，比-O1-版本更短更快

-m32-O3生成的代码复杂得多，涉及MMX寄存器上的SIMD指令……可能比-O2“版本更快，但完全过度设计，因为一个简单的小查找表不需要单独测试就足够了：

int Factorial(int n) {
    static int f32[16] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320,
                           362880, 3628800, 39916800, 479001600,
                           0, 0, 0 };
    return f32[n & 15];
}

请注意如何利用未定义的行为语义学（任何事情）来简化实现并删除测试。编译器被允许这样做，其中一些确实这样做了。