此递归函数的每次迭代的值存储在哪里?

Question

这个递归函数如何在 return 语句中工作 - 每次迭代的值存储在哪里？例如：val = 5. 当函数完成时，阶乘返回为 120.我正在使用cout<<factorial(5) <<endl;调用函数

// recursive factorial function.
int factorial(int val)
{
if (val > 1)
{
return (factorial(val-1) * val);//gets called 4 times
}
return 1;
}

Answer 1

现代 CPU 使用堆栈来处理函数的局部变量和返回地址(这是由 Algol 及其继任者提示的，以便能够干净地处理递归(。每个当前正在执行的函数都会获取一个激活记录，其中包含在堆栈上分配的局部变量(包括参数(和返回地址。您询问的值属于激活记录中的值(它不仅包括您定义的变量，还包括编译器为自己的目的创建的临时值(。

查看正在发生的事情的一种方法是让您的编译器编写汇编语言(甚至可以添加调试信息，它的文本可以通过提供指向源代码的指针来帮助破译汇编语言(。 例如：

clang++ -S -g factorial.cc

给factorial.s.

Answer 2

为了补充其他答案，我想补充一点，在更抽象的层面上，每次调用函数都会在运行时堆栈上创建一个额外的激活记录。对于递归函数，每个递归调用将有多个激活记录。在我们想要5!的示例中，运行时堆栈这部分的一些代表性伪代码可能如下所示(从下到上(：

int factorial(int val = 1){ /*returning 1*/ }

int factorial(int val = 2){ /*returning 2 * factorial(1)*/ }

int factorial(int val = 3){ /*returning 3 * factorial(2)*/ }

int factorial(int val = 4){ /*returning 4 * factorial(3)*/ }

int factorial(int val = 5){ /*returning 5 * factorial(4)*/ }

然后，一旦你到达基本情况，这个过程就完成了，回到堆栈(在val = 1的情况下，你返回1;现在当val = 2时，你可以返回2 * 1 = 2;然后当val = 3时，你可以返回3 * 2 = 6;然后返回4 * 6 = 24;最后返回5 * 24 = 120;并且，随着每次返回被执行， 相应的激活记录将从堆栈中弹出，直到最终答案返回到调用它的位置。