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

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

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

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

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

但是，如果能轉(zhuǎn)化為尾遞歸形式，并且你所使用的語(yǔ)言的編譯器具有對(duì)尾遞歸的優(yōu)化，那么尾遞歸的效率應(yīng)該至少應(yīng)該和循環(huán)一樣好。當(dāng)然，Java的編譯器一般來(lái)說(shuō)是不會(huì)對(duì)尾遞歸做優(yōu)化的。第二，對(duì)于有些不能轉(zhuǎn)化為尾遞歸形式的遞歸，即使你寫成了循環(huán)的形式，其實(shí)也基本上是在拿個(gè)棧來(lái)模擬遞歸的過(guò)程?？赡軙?huì)帶來(lái)一定的效率提升，但是往往會(huì)造成代碼的冗余。從開(kāi)發(fā)效率角度來(lái)考慮，除非性能實(shí)在達(dá)不到要求，否則還是建議使用遞歸的方式。

延伸閱讀：

二、遞歸算法是什么

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