對許多程式人來說,遞迴是既熟悉又陌生的思考方式,一層又一層的堆疊與狀態常令人卻步。然而,基於遞迴的碎形圖案,又經常美得讓人驚嘆。另外,在數學上,碎形還隱藏非整數維度的存在事實。
不過,無論遞迴、碎形或數學,其實一開始都是基於簡單的想法。
構造遞迴時的觀察
程式人對遞迴存在著許多誤解,最常見的遞迴解釋之一是「自己呼叫自己」,也許就是最大的誤解。
在遞迴時,對於此次任務與下次任務而言,兩者應該是獨立的,並非自己呼叫自己,而是此次任務與下次任務使用相同的定義求解。我先前專欄〈遞迴的美麗與哀愁〉也曾談過對遞迴的一些誤解,其中包含的數列加總範例,就是如此,其實每次的任務就只是「元素加上子數列總和」。
許多人對遞迴卻步的原因,或許是在於,無法想像任務之間「相同的定義」是怎麼找出來的?
程式人都知道河內塔,在基本解法裡面,會在一個函式定義中,再執行三次同樣的函式定義(指定的引數不同)。單看解答中的演算法,你會覺得理所當然——求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))。
無論是遞迴、碎形或甚至是數學,其實呈現出來的思考過程與成果,都是一種從簡單到複雜的可能性。然而,許多人太在意這個可能性的結果,而不是尋求這個可能性的過程,因而誤解了遞迴,甚至是碎形或數學。
實際上,尋求可能性的過程就算最終未獲成果,也是彌足珍貴的,至少在過程中確切思考過,哪些方向是不可行的,而這也將成為下次思考的基礎,讓前往複雜的可能性增加。只要有這樣的想法,遞迴、碎形與數學,就不再會是令人卻步的東西了。
專欄作者
熱門新聞
2024-11-04
2024-11-02
2024-11-04
2024-11-04
2024-11-04
2024-11-01