recursion - 递归中的中间结果如何以及在哪里存储？

Question

我试图了解递归在解释器方面是如何工作的。因此，我在 R 中实现了一个简单的递归函数：

> fac <- function(x) {
+   print(x)
+   if(x==0) return(1)
+   else {x*fac(x-1)}
+ }
> 
> fac(4)
[1] 4
[1] 3
[1] 2
[1] 1
[1] 0
[1] 24
> 

我了解递归本身，但不了解解释器如何存储中间结果。在这个例子中，我们从fac(4)which 基本上返回4*fac(3)then开始3*fac(2)，以此类推。但是这些临时结果存储在哪里或如何存储？一旦函数进行了最终调用，1*fac(0)它仍然需要总结先前调用的结果。但同样，这些必须事先存储或保存在内存中。我希望我想问的问题是可以理解的。不知道如何正确解释...

Answer 1

每个调用的状态都保留在堆栈中。所有代都有自己的 x 版本，除了基​​本情况之外的每一代都在较低的递归完成后进行乘法运算。这称为延续，使此递归函数无法进行尾调用优化。乘法发生在基本情况命中后的展开侧。

如果您在基本情况下有 return 但没有return x*fac(x-1). 似乎不一致。