為什麼尾遞歸優化似乎不常出現在非函數式語言的解釋器、編譯器中？

11-25

把用scheme寫的project euler的題目改成了perl版本，結果報了deep recursion的warning，為什麼尾遞歸優化沒有被解釋器、編譯器廣泛採用呢？

雖然好像perl可以用goto實現尾遞歸的樣子……

這一點可以從很多角度來分析。

ABI
操作系統的ABI定義了應用程序與操作系統之間的底層交互中的細節，比如函數調用協定等等。以System V AMD64 ABI為例，它要求在調用函數的時候，第七個以及往後的int型參數必須使用調用者的棧來傳遞。函數的返回地址，以及保存起來的幀指針，則擺在被調用者的棧的開頭。圖例：

然後當被調用的函數想要在尾部調用另一個函數，返回新函數的返回值（也就是尾調用）時，根據新函數的參數數量的不同，尾調用優化後的棧可以是這樣：

也可以是這樣：

總而言之，棧上免不了一些移動。這樣就浪費了處理器的一些循環，影響了運行效率。

調用信息
尾調用優化的語言，無法提供準確的調用信息，這會讓除錯變得很不方便。另外，沒有調用信息的話，依賴調用信息的一些功能，比如一部分的異常處理機制，JVM的許可權機制，也會變得無法使用。

不符合語言的通常做法
比如BDFL就認為，做一件事情必須要有且只有一種最好的方式去做。他覺得，既然能迭代，為啥還要用尾遞歸呢？

第一，懶。

第二，你以為有多少程序員會把函數寫成尾遞歸形式？（沒錯我說的就是JAVA程序員

我覺得認識到一個函數是尾遞歸的成本遠大於你直接把他寫成迭代的成本。。。
萬一寫錯了棧爆了怎麼破。。。
萬一別的程序員改了改，改跪了怎麼破。。。
所以命令式的程序員盡量不用尾遞歸，自然就不會默認優化尾遞歸了。。。
PS：C++各主流編譯器貌似都有尾遞歸優化的。。。

既然你問題里提到了perl，而且提到了

goto NAME

那尾遞歸優化省了call frame之後

caller EXPR

結果上哪兒找去啊。也就是說語言在提供諸多反射的特性的同時，尾遞歸優化已經不再是對行為沒啥影響的優化了，從取捨上說，尾遞歸在這些語言里真沒啥地位……

perldoc正好也提到了：

The "goto NAME" form is quite different from the other forms of
"goto". In fact, it isn"t a goto in the normal sense at all, and
doesn"t have the stigma associated with other gotos. Instead, it
exits the current subroutine (losing any changes set by local())
and immediately calls in its place the named subroutine using the
current value of @_. This is used by "AUTOLOAD" subroutines that
wish to load another subroutine and then pretend that the other
subroutine had been called in the first place (except that any
modifications to @_ in the current subroutine are propagated to
the other subroutine.) After the "goto", not even "caller" will be
able to tell that this routine was called first.

gcc就支持啊，儘管支持得不太完整。

我真覺得只是「懶」。這個「懶」也不是什麼貶義，只是在需求不強的前提下簡化實現。

除了簡化編譯器實現，沒覺得實現尾遞歸有什麼技術上的優點和難度。

關於棧的處理。要注意，實現 general 的尾調用可能有難度。但是實現尾遞歸真沒什麼難的。
關於調試信息。注意尾遞歸不是普通遞歸。一般場合用不到，也很容易避開。用到的場合一般都有比較清晰的理論模型。調試信息不是個大問題。

對非函數式語言來說，加了這個優化的話，對調試是不方便的。
想像你下了個斷點，到了對應行之後，查看堆棧，發現中間的調用信息都被吃掉了是什麼感覺......
另外在非函數式編程中這個需求真心不大。

順便如果你用gcc或vc的話開編譯優化尾遞歸是會編譯成jmp而不是call的

Java書上有寫的。
尾遞歸只是一個技術。
別人不一定想用。
一般他們喜歡迭代。

動態腳本語言禁止了很多種優化的可能，比如說函數名不是一個常量，它存在運行時被修改的可能，

function silly_repeat(action, n)
if n==0 then
return
else
action()
silly_repeat(action, b-1) -- 尾遞歸？
end

如果 action里重定義了位於全局表裡的 silly_repeat，編譯器不能假設這裡能優化成迭代