一、什么是遞歸？

1.遞歸是一種非常高效、簡(jiǎn)潔的編碼技巧，一種應(yīng)用非常廣泛的算法，比如DFS深度優(yōu)先搜索、前中后序二叉樹遍歷等都是使用遞歸。

2.方法或函數(shù)調(diào)用自身的方式稱為遞歸調(diào)用，調(diào)用稱為遞，返回稱為歸。

3.基本上，所有的遞歸問題都可以用遞推公式來表示，比如

f(n) = f(n-1) + 1;?

f(n) = f(n-1) + f(n-2);

f(n)=n*f(n-1);

二、為什么使用遞歸？遞歸的優(yōu)缺點(diǎn)？

1.優(yōu)點(diǎn)：代碼的表達(dá)力很強(qiáng)，寫起來簡(jiǎn)潔。

2.缺點(diǎn)：空間復(fù)雜度高、有堆棧溢出風(fēng)險(xiǎn)、存在重復(fù)計(jì)算、過多的函數(shù)調(diào)用會(huì)耗時(shí)較多等問題。

三、什么樣的問題可以用遞歸解決呢？

一個(gè)問題只要同時(shí)滿足以下3個(gè)條件，就可以用遞歸來解決：

1.問題的解可以分解為幾個(gè)子問題的解。何為子問題？就是數(shù)據(jù)規(guī)模更小的問題。

2.問題與子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣

3.存在遞歸終止條件

四、如何實(shí)現(xiàn)遞歸？

1.遞歸代碼編寫

寫遞歸代碼的關(guān)鍵就是找到如何將大問題分解為小問題的規(guī)律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼。

2.遞歸代碼理解

對(duì)于遞歸代碼，若試圖想清楚整個(gè)遞和歸的過程，實(shí)際上是進(jìn)入了一個(gè)思維誤區(qū)。

那該如何理解遞歸代碼呢？如果一個(gè)問題A可以分解為若干個(gè)子問題B、C、D，你可以假設(shè)子問題B、C、D已經(jīng)解決。而且，你只需要思考問題A與子問題B、C、D兩層之間的關(guān)系即可，不需要一層層往下思考子問題與子子問題，子子問題與子子子問題之間的關(guān)系。屏蔽掉遞歸細(xì)節(jié)，這樣子理解起來就簡(jiǎn)單多了。

因此，理解遞歸代碼，就把它抽象成一個(gè)遞推公式，不用想一層層的調(diào)用關(guān)系，不要試圖用人腦去分解遞歸的每個(gè)步驟。

五、遞歸常見問題及解決方案

1.警惕堆棧溢出：可以聲明一個(gè)全局變量來控制遞歸的深度，從而避免堆棧溢出。

2.警惕重復(fù)計(jì)算：通過某種數(shù)據(jù)結(jié)構(gòu)來保存已經(jīng)求解過的值，從而避免重復(fù)計(jì)算。

六、如何將遞歸改寫為非遞歸代碼？

籠統(tǒng)的講，所有的遞歸代碼都可以改寫為迭代循環(huán)的非遞歸寫法。如何做？抽象出遞推公式、初始值和邊界條件，然后用迭代循環(huán)實(shí)現(xiàn)。