今天我們來介紹一種很常見的算法——遞歸。

什麼是遞歸？簡單的說，遞歸就是通過不斷調用自己，來完成不斷循環的一個過程。

可能概念有些拗口，我們編寫一個遞歸函數來說明。斐波那契數列大家都知道，它從第三項開始，每一項都是前面兩項的和：

1,1,2,3,5,8,13,21......

我們就用遞歸的思想來實現上面這個數列。

我們假設遞歸函數為f(x)，在編寫遞歸函數時，要注意兩點。

一是給定基本情況，這裡的基本情況就是f(1)=1，f(2)=1。

二是确定規則，這裡的規則就是f(x)=f(x-1) f(x-2)。

好了，現在我們可以進行函數的編寫了：

OK，大功告成！是不是感覺很簡單呢？我們來簡單分析一下上面的代碼：

首先，定義了一個函數叫f(x)。def是define的縮寫，意思就是定義。f(x)中的x是項數，表示第幾項，比如我們想知道斐波那契數列的第5項是什麼，那麼x=5。

其次，由于f(1)和f(2)的值都是1，可以把它們合并成x<=2的條件，返回1。

最後，當x>2的時候，返回的就是前兩項的和，此時的f(x-1)和f(x-2)才有意義。

可能說了這麼多，你還是會有疑問，那麼我們就來舉個實例來看下上述代碼的運行過程吧。

比如我們想知道f(5)的值，因為5>2，因此返回前兩項的和f(4) f(3)。

那f(4)和f(3)又分别等于多少呢？先來看f(3)，因為3>2，因此返回f(2) f(1)=1 1=2；再來看f(4)，因為4>2，因此返回f(3) f(2)=[f(2) f(1)] f(2)=1 1 1=3。

因此，f(5)=f(4) f(3)=3 2=5。調用我們編寫的函數來驗證一下：

我們再來看一個遞歸的實際應用——漢諾塔遊戲。

如上圖所示，有3跟杆子A、B、C，其中A上有大小不一的3個圓環，越在下面的圓環越大。我們的目标是，按照現在的順序把3個圓盤從A挪到C。其中，有2個規則限制：

1.每次隻能移動一個圓盤。

2.大的圓盤不能放在小的圓盤上面。

我們先從簡單的情況看起吧，假如隻有1個圓盤，那很容易，直接把圓盤從A移到C即可。

那2個圓盤的情況呢？我們畫個圖來說明：

如上圖，有1、2兩個圓盤，要想把2号圓盤移到C，那麼首先需要移動1号圓盤。那1号移到哪裡合适呢？很容易看出，1号移到B，那麼下一步2号就可以直接移到C；如果1号移到C，那麼2号還需要先到B再到C。因此，最快的方法是把1移動到B。

然後，我們就可以把2号圓盤移動到C。

最後，隻需要把1号圓盤從B移到C即可。

好，我們來總結一下2個圓盤時的移動步驟。總共需要3步：第1步，把小圓盤從A移到B；第二步，把大圓盤從A移到C；第三步，把小圓盤從B移到C。我們要牢記這3個步驟，這是之後推理的基礎。

接下來，我們就來看3個圓盤的情況。

我們來思考一下，要想把3個圓盤從A移到C，首先需要把3号上面的圓盤1和2移到B，這樣3号才能直接到C。

關鍵的時刻來了，我們把1、2兩個圓盤移到B，不就是我們之前讨論的2個圓盤的情況嗎？隻不過之前的目标是從A移到C，現在是從A移到B，同樣是2個空着的杆子，僅僅是編号有差别，本質沒有任何區别！

理解了上面的核心内容，我們的思路就變得清晰了。3個圓盤同樣可以認為是3大步：第1步，把1和2移到B；第2步，把3移到C；第3步，把1和2從B移到C。而其中1和2如何移到B或者C，就是我們之前讨論的2個圓盤的情況了，這也就是遞歸的思想。

把上面的例子再拓展一下，如果是n個圓盤呢？

如上圖，A上有n個圓盤，我們要把它按這個順序移到C上。

就跟把大象關進冰箱需要3步一樣，我們這個也隻需要3步：第1步，把A中從1到n-1個圓盤移到B；第2步，把A中剩下的第n個圓盤移到C；第3步，把B中的n-1個圓盤移到C。至于如何把n-1個圓盤移到B，那就相當于重複我們上面的步驟，直到遞歸到我們熟悉的2個或3個圓盤所需的移動步驟。

好了，這就是今天的全部内容，歡迎留言讨論。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!