遞迴、碎形與數學

對許多程式人來說，遞迴是既熟悉又陌生的思考方式，一層又一層的堆疊與狀態常令人卻步。然而，基於遞迴的碎形圖案，又經常美得讓人驚嘆。另外，在數學上，碎形還隱藏非整數維度的存在事實。

不過，無論遞迴、碎形或數學，其實一開始都是基於簡單的想法。

構造遞迴時的觀察

程式人對遞迴存在著許多誤解，最常見的遞迴解釋之一是「自己呼叫自己」，也許就是最大的誤解。

在遞迴時，對於此次任務與下次任務而言，兩者應該是獨立的，並非自己呼叫自己，而是此次任務與下次任務使用相同的定義求解。我先前專欄〈遞迴的美麗與哀愁〉也曾談過對遞迴的一些誤解，其中包含的數列加總範例，就是如此，其實每次的任務就只是「元素加上子數列總和」。

許多人對遞迴卻步的原因，或許是在於，無法想像任務之間「相同的定義」是怎麼找出來的？

程式人都知道河內塔，在基本解法裡面，會在一個函式定義中，再執行三次同樣的函式定義（指定的引數不同）。單看解答中的演算法，你會覺得理所當然——求n盤的移動時，就是先看成只有n-1盤移到中柱，接著最大盤移到目標柱，然後，再將n-1盤從中柱移到目標柱。現在，假設沒看過這個解答，你如何知道要這麼想呢？

從複雜中找規則很難，然而，從簡單中找規則會比較容易。處理複雜問題的第一步，就是找出這個問題最簡單的一個狀況，寫出解法，然後，增加一層複雜，再予以解決，接著再加深複雜……在完成的解法中，試著找出重複的模式。

像是河內塔的最簡單狀況是只有一個盤子，寫出程式碼解決它，接著兩個盤子呢？再來三個盤子呢？隨著解法程式碼的增加，應該可以觀察出一些模式了，然後，試著重構它，就會得到你的遞迴解法，而且不一定是與上一段中描述的解法相同。

太常從已完成的解法中回頭理解，其實是學習遞迴的一大障礙，而在還沒解法之前進行觀察的過程，才是最重要的。

試試看，有個數列1,1,2,3,5,8,13,21,34, 55,89……試著找出規則吧！也許這太簡單了，因為許多人都玩過費式數列，也一開始就知道規則就是Fn = Fn-1 + Fn-2，那麼1,2,2,3,5,7,10,15,22,32,47……呢？

構造碎形時的觀察

方才的數列觀察出來了嗎？因為只是將費式數的規則做了簡單的調整，應該有人看出是Fn = Fn-1 + Fn-3！那麼，再來看一個有趣的數列，其中，除了第一個數之外，接下來遇到第一個1刪去、遇到第一個2刪去……，遇到第一個n刪去，結果會如何呢？

1,1,1,2,1,2,3,1,2,4,3,1,5,2,4,6,3,1,7,5,2,8,4,6,9,3,1,10,7,5,11,2,8,12,4,6,13,9,3

,14,1,10,15,7,5,16,11,2,17,8,12,18,4,6,19,13,9,20,3,14,21,1,10,22……

把得到的新數列跟原數列比比看，結果是一樣的喔！也就是數列中的子數列有自我相似性（self-similar）——子數列是整體縮減後的數列，這被稱為碎形數列（fractal sequence）。現在若要從無到有，產生這個數列，你能找出數列的產生規則嗎？

談到碎形，不少程式人並不陌生，多半也看過科赫（Koch）、樹木、蕨葉曲線，或者是謝爾賓斯基三角形（Sierpinski triangle）、茱莉亞集合（Julia set）等美麗的碎形圖案。維基百科〈Koch snowflake〉條目中，有個Zooming into the Koch curve動畫，一看就能知道何謂碎形圖案的自我相似性，感覺很神奇，這些碎形圖案怎麼構想出來的？

找個碎形來觀察吧！別急著看程式碼怎麼寫的，先辨識出碎形中最簡單的圖案是什麼。

以謝爾賓斯基三角形為例，最簡單的，當然是一個三角形有個挖空的三角形！因此就有三個未挖空的三角形了，接著，在正上方的三角形中，是個與目前圖案相同，只是小一號的圖案，這表示目前圖案的程式碼可以獨立出來，重複執行繪圖；類似地，也在左下、右下三角形中重複繪製，持續這個過程，就能產生謝爾賓斯基三角形了。

碎形背後的一些數學

相對於碎形數列，碎形圖案因為有具體的圖像，因而更容易觀察。試試科赫（Koch）、樹木、蕨葉曲線吧！別急著遞迴，先直接畫出最簡單的圖案，再逐次增加層次找出規則。

除了二維的圖案之外，也可以試著觀察該圖案是否可用三維來呈現，像是三維的樹木曲線、立體的謝爾賓斯基三角形如何建立等。

既然談到了維度，那麼，順便來談談碎形的維度吧！許多人都知道線段存在於一維空間，正方形存在於二維空間，而我們生活在三維空間中，就大部份人而言，整數維度是理所當然之事，然而，你能想像1.585維是什麼樣的世界嗎？這彷彿是在哈利波特小說中，初次看到九又四分之三月臺一樣，不過，謝爾賓斯基三角形的維度就近似於1.585，也就是說，如果謝爾賓斯基三角形可以無限制地延續下去，那麼它既不是線段，也不是平面。

碎形（Fractal）這名詞，是由數學家Benoit Mandelbrot在1975年提出，在這之前，他發表過的一篇論文《英國的海岸線有多長？統計自相似和分數維度》中，就談到了存在著非整數的維度。

關於這部份，我們可以從簡單的維度開始。取一條線段，需要「2」個複製品，才能讓線段成為「2」倍，而使之自相似，2為2的1次方，維度為1；若取一正方形，將需要「4」個複製品，讓此正方形成為「2」倍，而使之自相似，4為2的2次方，維度為2；若給一個正立方體，需要「8」個複製品，才能使尺度成為「2」倍，而使之自相似，也就是8為2的3次方，維度為3。

從上面的觀察規則看來，若給一個三角形，需要「3」個複製品，才能使尺度成為「2」倍，而使之自相似，2的d次方為必須為3，那麼d就是log(3)/log(2)近似於1.585。

若無法想像分數維度是怎麼回事，那就這麼思考吧！一個中間挖空的三角形是2維圖形，然而，一個「無限制地」在剩餘三角形中挖空的三角形，還能說是2維圖形嗎？它應該是在1維與2維之間的圖案！

複雜的可能性與過程

一個有趣的問題是「謝爾賓斯基三角形的面積是多少？」若真可以無限制繪製謝爾賓斯基三角形，那麼，它無法計算面積（在面積的定義中，圖形必須是2維才能計算面積），這樣大概可以想像「從碎形延伸而來的分數維度」是怎麼一回事。談到這邊，不禁懷疑，J.K.羅琳是否看過碎形相關資料？

回過頭來，剛剛那個碎形數列的規則，觀察出來了沒呢？想像有無限多個空盒組成一列，每個空盒只可以放一個球，球上各有數字1、2、3、4……，球依數字的增加，每間隔兩個空盒放入，例如1,_,_,2_,_,3,_,_4,_,_,5,_,_……，接下來，重新放入球1、2、3、4……，一樣要間隔兩個空盒，也就是1,1,_,2_,2,3,_,_4,3,_,5_,4……，接下來重新放入球1、2、3、4……，一樣要間隔兩個空盒……，不斷重複下去，就可以得到先前的碎形數列了（程式實現可參考我寫的Gist（https://goo.gl/HcFKWI））。

無論是遞迴、碎形或甚至是數學，其實呈現出來的思考過程與成果，都是一種從簡單到複雜的可能性。然而，許多人太在意這個可能性的結果，而不是尋求這個可能性的過程，因而誤解了遞迴，甚至是碎形或數學。

實際上，尋求可能性的過程就算最終未獲成果，也是彌足珍貴的，至少在過程中確切思考過，哪些方向是不可行的，而這也將成為下次思考的基礎，讓前往複雜的可能性增加。只要有這樣的想法，遞迴、碎形與數學，就不再會是令人卻步的東西了。