https://www.zhihu.com/video/960279818009505792

文章的開頭為什麼筆者會說遞歸可以體現代碼之美呢？ 看看開始的這個小視頻吧，它不僅僅比較好玩，而且可以體現遞歸的邏輯，那麼，下面讓我們來看看遞歸與循環吧。

一 什麼是遞歸 ？

大家通常把調用自身的函數稱作運用了遞歸。遞歸最精髓的思維便在這 遞 與 歸 ，遞 ： 顧名思義，便是問題不斷往下深入或者說不斷被分解 。 歸 ： 便是將分解到終點或者說我們給定的臨界點的時候完成簡單問題的解決並且回溯解決上一個問題直到解決我們最初始的問題。

二 為什麼要用遞歸或者說什麼時候應該運用遞歸？

在筆者看來

1 當一個問題可以被不斷分解為一個個更加簡單的問題的時候，並且在最終會有一個明確的終點的時候，這個時候便是考慮運用遞歸的時候了。舉一個栗子 ： 非常經典的斐波納契數列，又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8、13、21、…… 在數學上，斐波納契數列以如下被以遞歸的方法定義：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。

//這裡我們用兩種遞歸方法來解決，一種是最初的簡單遞歸，二是對簡單遞歸的優化 這裡我們用c++來實現

int fib(int n)//求出數列第n項的數值
{
if(n==1||n==2)
return 1;//回溯的條件
else
return fib(n-1)+fib(n-2);//向下遞進
}
這裡我們看 fib(5) = fib(4)+fib(3)
fib(4) = fib(3)+fib(2) fib(3) = fib(2)+fib(1).....
這裡有很多的計算是重複的，所以這也是遞歸的缺點之一
在這裡我們可以看到遞歸的思路，第n項為前兩項的和，那麼我們便可以不斷地向前推進直到已知項
這裡還有一種對於上述遞歸解法的優化方法
我們看前幾項分別為1 1 2 3 5
fiber(1,1,5) = fiber(1,2,4) = fiber(2,3,3)
解釋上述表達式 前兩項分別為1 1的第五項與前兩項分別為 1 2的第四項與前兩項分別為 2 3 的第3項相等 所以我們運用這種思路來避免重複的計算來降低計算的複雜度
代碼如下
int fiber(int first,int second,int num)
{
if(n>0)
{
if(num==1||num==2)
return 1;
else if(num==3)
return first+second;
else
return fiber(second,first+second,--num);
}
else
return -1;
}

2 當問題的設計是基於遞歸的，或者說問題只能用遞歸解決的時候 ， 例如 漢諾塔問題

古代有一個梵塔，塔內有三個座A、B、C，A座上有64個盤子，盤子大小不等，大的在下，小的在上。 有一個和尚想把這n個盤子從A座移到C座，但每次只能允許移動一個盤子，並且在移動過程中，3個座上的盤子始終保持大盤在下，小盤在上。在移動過程中可以利用B座。要求輸入層數，運算後輸出每步是如何移動的。

void HANIO(int n,char start,char depend,char final)
{
if(n==1)//結束條件
{
cout<<start<<" move to "<<final<<endl ;
return;
}
if(n>1)
{
HANIO(n-1,start,final,depend);
cout<<start<<" move to "<<final<<endl;
HANIO(n-1,depend,start,final);
return ;
}
}
每一次都是重複問題的推演，問題的設計思路便是遞歸的思路


3 數據結構便是遞歸形式的

例如二叉樹的遍歷，如果不瞭解二叉樹的同學可以看我開頭的短視頻，細心地同學可以看到每個三角形的填充都是右 到 左 到 上 ，它先不斷地縮小到最右側的最小的三角，然後不斷填充比他更大一號的三角，最終成為一個完整的三角形，二叉樹的形式於此大同小異，其數據結構決定了遞歸的優勢所在

三 遞歸應該具有什麼樣的條件呢？

我認為一個完整的遞歸應該有下面三個條件，否則就是不合格的遞歸

1 明確遞歸的終止方法（一個遞歸必須有他遞推到頭的界定，否則將會是無限遞歸 ）

2 明確的終止時處理方法

3 重複調用自身並縮小問題規模

四 遞歸和循環相比有何優缺點與異同

遞歸優點：

1 代碼可讀性高，程序簡潔

2 在解決特殊問題如二叉樹問題，漢諾塔問題是有著自己天然的優勢

遞歸缺點 ：

1 遞歸由於是函數調用自身，而函數調用是有時間和空間的消耗的：每一次函數調用，都需要在內存棧中分配空間以保存參數、返回地址以及臨時變數，而往棧中壓入數據和彈出數據都需要時間

2 遞歸中很多計算都是重複的，由於其本質是把一個問題分解成兩個或者多個小問題，多個小問題存在相互重疊的部分，則存在重複計算，如斐波那契數列的遞歸實現

3 調用棧可能會溢出，其實每一次函數調用會在內存棧中分配空間，而每個進程的棧的容量是有限的，當調用的層次太多時，就會超出棧的容量，從而導致棧溢出

這裡我們 穿插 著簡述一下什麼 是棧內存：

棧：就是那些由編譯器在需要的時候分配，在不需要的時候自動清除的變數的存儲區。裡面的變數通常是局部變數、函數參數等。在一個進程中，位於用戶虛擬地址空間頂部的是用戶棧，編譯器用它來實現函數的調用

那麼棧內存 的溢出又是怎麼回事？為什麼死循環不會溢出而無限遞歸會出現 溢出情況 呢？

但是無論我們怎麼樣使用死循環，都不會報這種錯誤，只不過因為循環無法結束而無法顯示程序結束。這是為什麼 ？

就像我們缺點一所說的，棧會自動將不再使用 的語句所佔用的空間釋放，從而保證程序運行的正常，但是在遞歸中，當前次遞歸的變數及結果依靠下次的遞歸返回值，所以當前的 空間 便無法釋放，棧內存的空間有限，當棧內存的空間被 填滿的時候，就會出現上圖所示 程序 崩潰的 情況 。

說到這裡大家 應該對遞歸有了初步的瞭解，有的同學可能就會說：我感覺遞歸併不比循環厲害多少啊，算了 我還是用循環好了。

雖然在 一般的簡單性問題中遞歸都可以用循環代替並且程序的運行效率還會高出不少，但是我們都不想 單單解決簡單的問題對吧，例如 我在 開頭 所畫的圖形，那便是遞歸在分形中的運用，還有博弈樹的構建與選擇，等等問題都與遞歸息息相關，所以 遞歸 還是 我們不可或缺 的 重要 能力 哦 。

看完了覺得有幫助的同學，動動你們發財的小手，點個讚唄，權當對筆者的認同，手動比心。

推薦閱讀：

相關文章