計算機在執(zhí)行遞歸算法時效率低的原因是什么?

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

計算機在執(zhí)行遞歸算法時效率低的原因是函數(shù)調(diào)用的開銷導(dǎo)致的。在一個函數(shù)調(diào)用之前需要做許多工作，比如準(zhǔn)備函數(shù)內(nèi)局部變量使用的空間、搞定函數(shù)的參數(shù)等等。

這些事情每次調(diào)用函數(shù)都需要做，因此會產(chǎn)生額外開銷導(dǎo)致遞歸效率偏低，所以邏輯上開銷一致時遞歸的額外開銷會多一些

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

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

但是，如果能轉(zhuǎn)化為尾遞歸形式，并且你所使用的語言的編譯器具有對尾遞歸的優(yōu)化，那么尾遞歸的效率應(yīng)該至少應(yīng)該和循環(huán)一樣好。當(dāng)然，Java的編譯器一般來說是不會對尾遞歸做優(yōu)化的。第二，對于有些不能轉(zhuǎn)化為尾遞歸形式的遞歸，即使你寫成了循環(huán)的形式，其實也基本上是在拿個棧來模擬遞歸的過程?？赡軙硪欢ǖ男侍嵘峭鶗斐纱a的冗余。從開發(fā)效率角度來考慮，除非性能實在達不到要求，否則還是建議使用遞歸的方式。

延伸閱讀：

二、遞歸算法是什么

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