一、計算機在執行遞歸算法時效率低的原因

計算機在執行遞歸算法時效率低的原因是函數調用的開銷導致的。在一個函數調用之前需要做許多工作，比如準備函數內局部變量使用的空間、搞定函數的參數等等。

這些事情每次調用函數都需要做，因此會產生額外開銷導致遞歸效率偏低，所以邏輯上開銷一致時遞歸的額外開銷會多一些

當然了，通過有意識的組織代碼的寫法可以把某些遞歸寫成尾遞歸，尾遞歸可以進行特殊的優化所以效率會比普通的遞歸高一些，也不會因為遞歸太多導致棧溢出。

遍歷樹還不用遞歸的話，那么人肉寫一個棧+深度優先遍歷或者人肉隊列+廣度優先遍歷，再輔以黑魔法給棧或者隊列提速，應該會比遞歸快一些，加速幅度和語言和寫法相關，但在大多數情況下我覺得是得不償失的，花了很大精力很可能效率提升不明顯。

但是，如果能轉化為尾遞歸形式，并且你所使用的語言的編譯器具有對尾遞歸的優化，那么尾遞歸的效率應該至少應該和循環一樣好。當然，Java的編譯器一般來說是不會對尾遞歸做優化的。第二，對于有些不能轉化為尾遞歸形式的遞歸，即使你寫成了循環的形式，其實也基本上是在拿個棧來模擬遞歸的過程。可能會帶來一定的效率提升，但是往往會造成代碼的冗余。從開發效率角度來考慮，除非性能實在達不到要求，否則還是建議使用遞歸的方式。

延伸閱讀：

二、遞歸算法是什么

遞歸算法（英語：recursion algorithm）在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用于解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念。絕大多數編程語言支持函數的自調用，在這些語言中函數可以通過調用自身來進行遞歸。計算理論可以證明遞歸的作用可以完全取代循環，因此在很多函數編程語言（如Scheme）中習慣用遞歸來實現循環。