如何以及在哪裏存儲遞歸的臨時結果？

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)開始，它基本上返回4*fac(3)，然後3*fac(2)等等。但是，這些臨時結果在哪裏或如何存儲？一旦函數執行了最後的調用，即1*fac(0)，它仍然需要總結先前調用的結果。但是，這些必須事先存儲或保存在內存中。我希望這是我可以理解的問題。不知道如何正確解釋...

Answer 1

每個通話的狀態都保持在堆棧中。所有的世代都有它們自己的x版本，除了基​​本情況下，在較低的遞歸完成後進行乘法。這被稱爲延續使得這個遞歸函數不可能拖尾調用優化。乘法運算髮生在base case命中後的展開一側。

奇怪的語言，如果你有你的基本情況返回，但不是return x*fac(x-1)。似乎不一致。