遞歸有什么優(yōu)缺點?

一、遞歸的優(yōu)缺點

遞歸是什么

程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。遞歸做為一種算法在程序設計語言中廣泛應用。

一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。

遞歸的能力在于用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

遞歸的優(yōu)缺點

優(yōu)點：代碼更簡潔清晰，可讀性更好

遞歸的話函數(shù)調(diào)用是有開銷的，而且遞歸的次數(shù)受堆棧大小的限制。

缺點：

時間和空間消耗比較大。每一次函數(shù)調(diào)用都需要在內(nèi)存棧中分配空間以保存參數(shù)，返回地址以及臨時變量，而且往棧里面壓入數(shù)據(jù)和彈出都需要時間。

另外遞歸會有重復的計算。遞歸本質(zhì)是把一個問題分解為多個問題，如果這多個問題存在重復計算，有時候會隨著n成指數(shù)增長。斐波那契的遞歸就是一個例子。

遞歸還有棧溢出的問題，每個進程的棧容量是有限的。由于遞歸需要系統(tǒng)堆棧，所以空間消耗要比非遞歸代碼要大很多。而且，如果遞歸深度太大，可能系統(tǒng)撐不住。

延伸閱讀：

二、遞歸的程序特性

優(yōu)雅性

相比其他解法（比如迭代法），使用遞歸法，你會發(fā)現(xiàn)只需少量程序就可描述出解題過程，大大減少了程序的代碼量，而且很好理解。遞歸的能力在于用有限的語句來定義對象的無限集合。

反向性

由于遞歸調(diào)用程序需要維護調(diào)用棧，而棧（我們在上文提過）具有后進先出的特征，因此遞歸程序適合滿足取反類需求。我們在第五部分有一些編程實踐，比如字符串取反，鏈表取反等相關有趣的算法問題。

遞推關系

遞歸程序可以較明顯的發(fā)現(xiàn)遞推關系，反過來也可以這么說，具有遞推關系的問題基本都可以通過遞歸求解（當然也許有性能更佳的解法，但遞歸絕對是一種選擇）。遞推關系常見問題有楊輝三角、階乘計算。