沒有了這個規則，自然界再也不可能發現美麗的分形

遞歸思想

是一個自然界運行法則

1

漢諾塔

古印度神話故事中，在大梵天創造世界的時候，為了考驗人類，做了三根金剛石柱子，在其中一根柱子上從下往上按照大小順序摞著64片黃金圓盤。

大梵天便命令教徒把圓盤按大小順序重新擺放在另一根柱子上，但他還規定了一個規則：在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

大梵天對教徒們預言：當你們完成移動的那一刻，就是這個世界終結的時候。

1883年，法國數學家édouard Lucas有一次碰巧聽到這個故事，無聊中的Lucas開始思考怎麼玩，然而Lucas發現移動64層圓盤的過程非常繁雜，腦袋根本無法承載這麼大的計算量，便嘗試將問題進行簡化：把6個圓盤從一個柱子移動到另外一個柱子，最少需要多少步可以完成？

Lucas也給這個問題取名為漢諾塔問題。

漢諾塔問題示意圖

其實對於漢諾塔問題，大家都應該很熟悉。不過為了計算更簡便些，我們先嘗試漢諾塔問題只有3個圓盤的情況下應該怎麼做？這個估計大家在第一時間應該能夠反應出來，最後發現只需7步就可以完成。

3個圓盤的漢諾塔解法

當圓盤數量增加6個以後，這個時候可能就開始有點懵了：

6個圓盤的漢諾塔解法

可以發現，隨著圓盤數的增加，漢諾塔問題難度越來越大。不過人類最不怕的就是解決問題，針對漢諾塔問題，數學家們提出了一個非常巧妙解法，遞歸解法：

Step 1：將A柱子上的n-1個圓盤搬到B柱子上

Step 2：將A柱子上剩下的大圓盤搬到C柱子上

Step 3：將B柱子上的n-1個圓盤搬到C柱子上

遞歸解法的關鍵步驟：移動最大的圓盤到目的地

我們再考慮一下n-1個圓盤是怎麼從A柱子搬到B柱子上的。我們可以重複上述的過程，完全跟搬從A柱子把n個圓盤搬到C柱子的過程類似。

Step 1：將A柱子上的n-2個圓盤搬到C柱子上

Step 2：將A柱子上第n-1個大圓盤搬到B柱子上

Step 3：將C柱子上的n-1個圓盤搬到B柱子上

移動的過程通過這種遞歸方式可以清晰描述出來，所以我們只需要從最頂層進行考慮。假設將n個圓盤從一個柱子全部搬到另外一個柱子上的最少移動次數是H(n)，那麼根據上面遞歸解法中的3步可以得到這個關係式：

這個遞推表達式已經非常明確了，我們可以利用這個遞推表達式，得到任意數量圓盤漢諾塔問題的最少移動步數。已知H(1)=1，進行一下推導以後我們得到：

代入算一下，H(3)=7，H(6)=63。而64層漢諾塔的最少移動次數是H(64)。假設移動1次需要1秒，需要5849億年才能完成移動，遠遠大於當前宇宙年齡138億年，吻合大梵天「預言」。估計大梵天早已洞悉這個問題的答案，靠人力來移動漢諾塔是一個不可能完成的任務，也就是說不可能世界末日。

一個看似複雜的問題，卻蘊含著如此巧妙的遞歸解法，令人驚嘆。漢諾塔在現代也成為了一款頗受歡迎的益智遊戲，在娛樂過程中給人們傳遞著蘊含其中的遞歸思想。

2

遞歸的來源

20世紀50年代，在計算機誕生以後，Fortran是最早得到廣的編程語言，Fortran源自於公式翻譯的縮寫（FormulaTranslation）。

Fortran是一個為計算而生的語言，但它的編譯系統並未科學地解決一些主要的難題，其中一個就是程序不能調用自身。（儘管如此，Fortran語言一直在發展，最新版是Fortran 2018，在科學與工程界享有盛譽。）

1960年，荷蘭計算機學家，艾茲格·W·迪傑斯拉克（Edsger Wybe Dijkstra）在他的著作《遞歸編程》（Recursive Programming）中首次明確描述可以在程序當中使用遞歸這個概念。

迪傑斯拉克遇到這麼個問題，如果每個子程序（subroutine）在啟動時都佔據固定的工作空間，將導致兩個後果。一是如果同時運行多個子程序，必將佔用大量的空間，空間使用效率低。二是，若有一個子程序已經在運行，在這個子程序結束以前，不能再調用自己。因為調用自己時數據無法與上一次調用分隔開。

為了解決這種情況，迪傑斯拉克鄭重地提出遞歸編程的概念（Recursive Programming）。

迪傑斯拉克獨立發明了逆波蘭記法（Reverse Polish notation，RPN），發展了棧（Stack）的概念，將棧的概念用於代碼運行時的動態存儲分配，實現遞歸調用子程序時的環境維護，在此基礎上與荷蘭程序員Jaap Zonneveld完成了ALGOL60的第一個版本，這是最早支持遞歸的高級語言。因為在ALGOL60上做出原理性貢獻，Dijkstra獲得了1972年的圖靈獎（小智寫過Dijkstra大神，感興趣點擊傳送門）。

圖靈獎盃（圖靈獎有計算機科學界諾貝爾獎之稱）

逆波蘭記法是什麼？

逆波蘭式將操作符號（operator）放在操作對象（operand）。我們可以用逆波蘭記法試著轉換一些簡單的式子：

3 + 4 這個式子，可以表示為：3 4 +

3 - 4 + 5 這個式子，可以表示為：3 4 - 5 +

3 - 4 + 5 × 6 這個式子，可以表示為：3 4 - 5 6 × +

3 - (4 + 5) × 6 這個式子，可以表示為：3 4 5 + 6 × +

在逆波蘭記法的作用下，在式子中不需要再使用括弧來表示計算先後順序。逆波蘭記法極大幫助了計算機對式子計算過程的理解，而實現逆波蘭記法需要藉助棧。換句話說，棧實際上可以表示多個層次的程序運算，即實現遞歸。

從此，程序員們多了一個新辭彙：遞歸。

3

什麼是遞歸

遞歸（Recursion），是指在函數的定義中調用函數自身的方法。在數學與計算機科學中有非常重要的地位，也是眾多公式與演算法思想的源泉。

首先，最直觀體現遞歸概念的公式是階乘。n的階乘，定義為1到n所有數的乘積。假設n的階乘結果為F(n)，我們可以將階乘定義成下面這個式子：

其中F(1) = 1。

可以發現，n的階乘可以用n-1的階乘來進行定義，用自己的定義來定義自己，這就是遞歸的思想。

另外一個例子是斐波那契數列（Fibonacci sequence）。斐波那契（Fibonacci）是12世紀的義大利數學家。他在他的著作《算盤全書》（liber abaci）中記錄了這樣一個問題：

假設在圍欄當中有一對剛出生的兔子（一隻雄性，一隻雌性）。這對兔子出生後的第二個月結束時開始可以生兔子，每個月可以生另外一對兔子（同樣包含一隻雄性，一隻雌性，生育模式與父母相同）。再假設兔子不會死亡，一直可以生長下去。問一年內可繁殖成多少對兔子？

我們詳細列一下每個月的情況：

第1個月，只有1對兔子

第2個月，還是1對兔子，還沒開始生兔子

第3個月，新增1對兔子，加上第2個月的1對老兔子，一共2對兔子

第4個月，兩個月前有1對兔子，可以生1對兔子，加上第3個月的2對兔子，一共有3對兔子

第5個月，兩個月前有2對兔子，可以生2對兔子，加上第4個月的3對兔子，一共有5對兔子

……

所以，兔子生長序列可以寫成下面這個數列：

1，1，2，3，5，8，13，……

可以發現，除了最前面的兩個數字以外，其餘的數字是前兩個位置的數字之和。上述的兔子繁殖序列，就是斐波那契數列。假設斐波那契數列的第n列為F(n)，那麼可以得到F(n)的遞推式：

其中，F(1) = 1，F(2) = 1

斐波那契數列非常著名，其中有一個神奇的特徵，隨著項數的增大，前項與後項之比越來越接近0.618，被稱為黃金分割點，是一個被人類廣泛使用的一個奇妙數字。

《蒙娜麗莎》當中的海螺線，處處體現了黃金分割比例

回到文章的開頭，在計算漢諾塔問題移動的步數時也得到了一個以自身定義的一個遞推式，運用了遞歸思想來解決問題。遞歸思想顯著幫助了對漢諾塔問題的描述和解答。

4

遞歸的應用

關於分而治之（Divide and conquer）

分而治之是計算機領域一個重要思想，重複遞歸手段解決問題。分而治之思想要求，想辦法將一個複雜的問題分解為多個子問題，直至這些問題可以被直接解決。所有子問題的計算結果綜合起來就是原問題的計算結果。簡單來說，分而治之思想就是遞歸思想的延伸。相當多的演算法都有分而治之思想的影子。

比如，排序演算法當中著名的歸併排序，就是利用了分而治之的策略（小智寫過歸併排序演算法，感興趣點擊傳送門）。它將排序結果定義為將兩個為原來規模一半的排序結果合併在一起。假設需要排序的規模是n，排序結果定義為F(n)，可以定義遞推式：

其中，G操作是把兩個排序結果合併成一個有序的結果。假如排序所需要的時間為T(n)，那麼可以定義所需要的計算時間為：

對於一個規模為n的排序問題來說，劃分次數是log2n次，推導可得T(n) = O(n log n)，歸併排序時間的時間複雜度屬於較好的水平了。

關於動態規劃（dynamic programming）

動態規劃是運籌學的一個分支（小智寫過動態規劃演算法，感興趣點擊傳送門）。如果單純是遞歸演算法，在某些情況下可能會出現非常多的相同子問題，這些子問題對計算效率有很大的影響。

比如，算斐波那契數列F(7)，以F(3)為舉例，最後要計算F(3)的次數竟然達到5次。隨著斐波那契數列的項數增加，若是單純用遞歸演算法，F(3)計算量必然呈指數級增長。實際上F(3)只需要計算1次就夠了，保存起來，需要的時候再調用即可。

對費波那契數列第7項進行計算涉及到的遞歸過程

簡單來說，動態規劃其實就是從這個角度對遞歸演算法進行延伸。動態規劃的精妙之處在於，每個子問題只求解一次，並將解保存在一個表格中，當需要再次求解此子問題時，只是簡單地通過查表獲得該子問題的解，避免大量的重複計算。

關於分形（Fractal）

這條看起來像一朵雪花的曲線，是科赫（Koch）曲線，無限放大後外觀上沒有變化，這就是一個分形結構。

分形是波蘭數學家本華·曼德博（Benoit Mandelbrot）於1975年創造出來的一個詞，其原意就是指不規則、破碎等，曼德博想用這個詞來描述自然界中傳統歐幾里德幾何學所不能描述的一大類複雜無規的幾何對象。

這些幾何對象具有自相似的性質，即它們可以分成數個部分，而每一部分都是整體縮小後的形狀，就像上圖的無限雪花那樣。

Koch曲線具備這樣的自相似特徵，那Koch曲線是怎樣畫出來的呢？

首先畫一個線段，然後把它平分成三段，去掉中間那一段並用兩條等長的線段代替。這樣，原來的一條線段就變成了四條小的線段。用相同的方法把每一條小的線段的中間三分之一替換為等邊三角形的兩邊，得到了16條更小的線段。然後繼續對16條線段進行相同的操作，並無限地進行下去。我們也可以把這個過程寫成一個遞推式，假設第n次迭代的圖形是F(n)，那麼：

其中G表示將圖形的所有線段進行Koch處理，F(1)表示最開始的那條線段。可以看出Koch曲線實際上由自己來定義，是一個簡單的遞歸過程。

諸如Koch曲線、樹枝生成等這些分形結構的產生可以運用某個特定規則，不斷進行遞歸，最終可以得到一個完全自相似的結構。

一棵分形樹

（圖片來源：http://robertfathauer.com/FractalTree9.html）

自然界當中存在大量的分形結構，比如樹枝、海岸線、山峰、閃電、貝殼、雪花、雲朵等等，形成分形的原因非常多。但我覺得有一個非常重要的原因，那就是分形的誕生源自遞歸，比如樹枝的不斷地進行同樣的生長過程、海岸線不斷地受到類似的海浪碰撞、山峰不斷地受到類似的風雨侵蝕，這些造就了形狀上的分形結構。自然界就是這樣的大環境，提供一個不受到干擾的自然演化場景，演化出了這些如此美妙的結構。往大自然更靠近一些，越會發現精彩之處。

分形演算法作品：山中晨曦

（圖片來源：http://blog.sina.com.cn/s/blog_5fd454d00100i0gu.html）

本文系網易新聞·網易號「各有態度」特色內容

部分資料來源於網路

轉載請在公眾號中，回復「轉載」

-----這裡是數學思維的聚集地------

「超級數學建模」（微信號supermodeling），每天學一點小知識，輕鬆了解各種思維，做個好玩的理性派。50萬數學精英都在關注！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！