一個長期被誤會的問題，這下說清楚了——迭代與遞歸的性能

遞歸真的會比迭代性能差嗎？

在《Racket指南》（2.3.4 遞歸和迭代）中，Racket的作者做了清晰的解釋：

在許多語言中，儘可能地將儘可能多的計算合併成迭代形式是很重要的。否則，性能會變差，不太大的輸入都會導致堆棧溢出。類似地，在Racket中，有時很重要的一點是要確保在易於計算的常數空間中使用尾遞歸避免O(n)空間消耗。

然而，在Racket里遞歸不會導致特別差的性能，而且沒有堆棧溢出那樣的事情；如果一個計算涉及到太多的上下文，你可能耗盡內存，但耗盡內存通常需要比可能觸發其它語言中的堆棧溢出更多數量級以上的更深層次的遞歸。基於這些考慮因素，加上尾遞歸程序會自動和一個循環一樣運行的事實相結合，引導Racket程序員接受遞歸形式而不是避免它們。

例如，假設你想從一個列表中去除連續的重複項。雖然這樣的一個函數可以寫成一個循環，為每次迭代記住前面的元素，但一個Racket程序員更可能只寫以下內容：

一般來說，這個函數為一個長度為n的輸入列表消耗O(n)的空間，但這很好，因為它產生一個O(n)結果。如果輸入列表恰巧是連續重複的，那麼得到的列表可以比O(n)小得多——而且remove-dups也將使用比O(n)更少的空間！原因是當函數放棄重複，它返回一個remove-dups的直接調用結果，所以尾部調用「優化」加入：

基於上述的描述，我們應該認真地重新認識遞歸的意義和價值，而且，在函數式編程中，你會發現用遞歸完成很多應用非常簡潔，甚至用迭代是難以實現的（會用相對複雜的代碼，而且可讀性變差）。

而且使用尾遞歸優化後，更是做到了性能與表達的完美結合。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！