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

遞歸是什么

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

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

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

遞歸的優(yōu)缺點(diǎn)

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

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

缺點(diǎn)：

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

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

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

延伸閱讀：

二、遞歸的程序特性

優(yōu)雅性

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

反向性

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

遞推關(guān)系

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