我试图从解释器的角度来理解递归是如何工作的。因此,我在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)开始,它基本上返回4*fac(3),然后是3*fac(2),依此类推。但是,这样的中期结果存储在哪里或如何存储?一旦函数执行了最后一次调用(即1*fac(0) ),它仍然需要对之前调用的结果进行求和。但同样,这些必须事先存储或保留在内存中。我希望我想问的问题是可以理解的。我不知道该怎么解释...
发布于 2013-10-08 06:55:14
每个调用的状态都保留在堆栈中。所有的世代都有自己的x版本,除了基本情况之外,每个世代都会在低级递归完成后进行乘法运算。这被称为延续,使得这个递归函数不可能尾部调用optimize。在基本情况发生后,乘法发生在展开侧。
如果你在你的基本情况下有返回值,但没有return x*fac(x-1),那就是奇怪的语言。看起来并不一致。
https://stackoverflow.com/questions/19228706
复制相似问题