Posted By Mr. Thursday & Mr. Saturday
(註：本篇文章有一點長，請耐心服用 XD)
想像一下，我剛才說了一句話，那句話是：「想像一下，我剛才說了一句話，那句話是：「想像一下，我剛才說了一句話，那句話是：……….」」，如此下去，就好像站在兩面平行擺設的鏡子中間，鏡子中的影像不斷的重複。再舉個例子，寫完一封信想要匿名保密，就署名「知名不具」。回信的人寫：「知 知名不具 具」。之後再回信的時候就變成：知知知名不具具具，加上括號可能比較清楚：(知(知(知名不具)具)具)。
遞迴就是類似這樣子，不斷的重複同樣的東西，只不過每次重複的是比較小的東西了。大家應該對數學歸納法不陌生，在使用數學歸納法時，我們首先確定 n=1 的時候某件事情是成立，然後在證明 n 到 n+1 的過程是正確的，就可以從 n=1 的例子，一路推論出第 n 項是甚麼東西。就像是推骨牌一樣，把第一張牌推倒了之後，剩下的骨牌自然就被前面的骨牌給推倒。
遞迴的概念則是相反的方向：我們想要解決一個大小為 n 的問題，我首先做的事情是把問題化簡成大小為 n-1 的問題，但是解決的方法還是一樣，只不過大小是 n-1。如此繼續化簡，最後變成大小為 n=1 的基本問題，接著只要n=1的基本問題解決了，原來大小為n的問題也跟著解決了。
這又好像層層分工。假設每個人都會加法，然後今天我想求出 1+2+…+n 等於多少？其中一個辦法就是遞迴，我先假設 1+2+…+(n-1) 已經有人算好，那麼我只要再加上 n，就可以得到答案了。然而 1+2+…+(n-1) 要怎麼得到呢？我就請另外一位朋友幫我算。另外一位朋友接到這個問題以後，也用同樣的方法，他把 1+2+…+(n-2) 的結果交給另外一位朋友算，然後把這個結果加上 (n-1)，就變成我想要的 1+2+…+(n-1) 了。朋友的朋友也繼續用類似的方法，直到最後一位朋友只需要回答1，接著倒數第二位朋友就把1加上2，傳給倒數第三位朋友，倒數第三位朋友加上3，一直到我收到 1+2+…+(n-1) 的結果，再加上 n，就大功告成了。
不過可能會覺得，如此簡單的問題，為何還需要遞迴呢？其實遞迴也是比較適合一些問題來解，也就是那些「解決方式一樣，但是可以化成大小比較小」的問題，除此之外還可以輕鬆解決基本問題(n=1的時候)。舉例來說，有個古老的問題叫做河內塔 (Hanoi Tower)，問題的定義引述如下 (引述網站)
1883年，一位法國的數學家 Edouard Lucas 教授在歐洲的一份雜誌上介紹了一個相當吸引人的難題──迷人的智力遊戲。這個遊戲名為河內塔 (Tower of Hanoi)，它源自古印度神廟中的一段故事 (也有一說是 Lucas 教授為增加此遊戲之神秘色彩而捏造的)。傳說在古老的印度，有一座神廟，據說它是宇宙的中心。在廟宇中放置了一塊上面插有三根長木釘的木板，在其中的一根木釘上，從上至下被放置了64片直徑由小至大的圓環形金屬片。古印度教的天神指示祂的僧侶們將64片的金屬片移至三根木釘中的其中一根上。規定在每次的移動中，只能搬移一片金屬片，並且在過程中必須保持金屬片由上至下是直徑由小至大的次序，也就是說不論在那一根木釘上，圓環形的金屬片都是直徑較小的被放在上層。直到有一天，僧侶們能將64片的金屬片依規則從指定的木釘上全部移動至另一根木釘上，那麼，世界末日即隨之來到，世間的一切終將被毀滅，萬物都將至極樂世界。
倘若這個故事的敘述為真，那麼，我們只需加速移動金屬片，是不是就能愈早到達極樂世界呢？果真要移動這64片金屬片，那麼，至少要花幾次的搬動才能完成呢？有沒有規律可循呢？
這個問題，就很符合剛才的特性：我們可以把大問題化成小問題，而且解決的方法相同，只不過問題的大小變小了。另外基本問題(n=1)，就是移動一根金屬片所需要的次數，這個我們也可以輕易解決，所以這個問題就可以用遞迴來解。
首先，我們假設有A、B、C三根柱子，這64片金屬片一開始在柱子A上面，我們想要搬到柱子C。因為問題中規定某個金屬片上面是空的時候才能移動，我們就假設有個人可以幫我們把63片比較小的金屬片先從柱子A搬到柱子B上面，然後我們把最大的那一片從柱子A搬到柱子C，再請那位朋友把剛才的63片從柱子B搬到柱子C，整個問題就解決了。然後我們只要知道剛才那位朋友搬了幾次，然後加上我們自己般動的1次，就是整個問題要求的搬動次數了。
遞迴不僅僅在數學上有其重要性，在電腦科學之中扮演的角色更是至關重要。程式設計者對於遞迴絕對不會陌生，上面所舉的河內塔問題，實際上也是電腦科學的經典例子之一，是初學程式設計的人一定會學到的東西。遞迴的思維，常常可以讓程式設計者打造出簡潔的程式，讓繁冗的問題透過簡單的程式碼來解決 (例如 parser 的設計)。演算法上所講的 dynamic programming，就是遞迴思維在演算法的具體呈現。
遞迴同時也是碎形 (fractal) 這門大學問的基石，碎形是一種相當美妙的幾何圖案，就如同上面那一張蒙娜麗莎的圖一樣，圖中有圖，形中有形，且小的部分都是大的部分的縮影，我們就稱之為碎形。碎形本身的數學定義，實際上就包含了遞迴定義在裡面，我們甚至於可以說，碎形是遞迴在幾何學的一種具體呈現。但是碎形不僅僅是一種數學概念而已，在自然界中，有許許多多的地方都出現自然的碎形，讓人讚嘆遞迴原來就出現在我們的生活周圍。圖中的這棵花椰菜，就蘊含了遞迴的碎形圖案與於其中。碎形同時也在各個研究領域有著廣泛的應用，光是在電腦科學領域，就有人把碎形應用在影像和影片壓縮之上 (這不難想像，由於碎形這種以小見大的特性，我們可以用小的來表現大的，因此可以有壓縮的概念出現)，在電腦圖學上 (computer graphics)，也有人把碎形應用在設計電腦遊戲之中的一些景物，打造出有效率和簡潔的系統。現在電腦遊戲之中的景物，很多都是玩家邊玩、遊戲系統邊產生出即時的景物，這叫做 procedural generation，這種即時產生景物的技術，可以避免遊戲軟體預先儲存一堆要展現的景物，幫整個軟體瘦身。procedural generation 就使用了大量的碎形產生與合成技術於其中，而這些都根植於遞迴這一個深刻卻簡單的思維。
至於把碎形應用在遊戲之中，現在已經做到有多可怕的地步了呢？請大家看看以下的三張圖片，不妨猜猜擁有這種精緻畫面的遊戲軟體，其整個遊戲的size大小是多少呢？
正確答案是97KB！沒錯，我沒有打錯字，你的眼睛也沒有看錯，這款遊戲的大小只有 97KB！傳統的一片 3.5 吋磁片可以裝下十幾個這款遊戲！這一款第一人稱的射擊遊戲叫做 .kkrieger，是由德國的 demogroup .theprodukkt 所開發，截至目前為止還在beta測試版的階段，這款遊戲之所以可以壓縮到這麼小的境界，就是因為遊戲之中的場景和音樂幾乎全部都是由動態產生，遊戲之中預先存放的資料只有一些簡單的幾何形狀和 MIDI 音樂檔，所以自然檔案大小非常小。如果這款遊戲沒有用 procedural generation 的技巧進來的話，估計檔案大小會爆增成 200~300MB，這樣的技術，真是令人嘆為觀止。而背後最大的功臣，就是這篇文章談到的遞迴和碎形。各位也不妨下載來玩玩看吧 (下載點)。不過需要注意到一件事情，這款遊戲的載入時間非常長，因為他要靠著一點點的程式碼即時來運算製造出場景，所以要耗去很多計算時間，這可說是一種 time 和 space 的 tradeoff。
看完這篇文章，各位有沒有對看似枯燥的數學有了一點點不同的看法呢？沒想到遞迴可以這樣應用在遊戲開發之中吧。下次學習數學感覺到枯燥時，不妨從應用的角度切入試試看吧！
過去的今天：
- 我所理解的東西，永遠不是它真正的涵義 - 2008
- fav.or.it - 透過 RSS Reader 創建社群 - 2008
- 你的視覺欺騙你 - 2007
- PC World 精選100 - 2007
- 認知與記憶 - 2007
相關推薦
 |
 |
訂閱 所有文章 (含專欄文章 + 產業新聞 + 其他文章)
不長不長,這是篇有趣的文章！
真懷念推演數學歸納法的感覺~
這篇文章不錯 那個FPS遊戲更有意思
Ha! It is “recursive”. I thought I was out-of-date for a while
[...] 遞迴之美: 數學, 電腦科學與碎形 (co-auther with Mr. Saturday) [...]
I like ths article.
輕鬆、簡潔又溫故的好文。
今年一月, 用遞迴的概念, 我們建構出一個新的紙本書籍傳遞方式, 可以用decentralized的方式,透過P2P人際網路,把書本傳到各個角落,包括偏遠地區, 在這邊簡單作個介紹, 供各位對遞迴有興趣的先進參考:
首先是拿出一本書, 在這本書的內頁寫下規則如下:
我拿這本書, 表示我同意:
(1) 把這本書繼續傳給同意此規則的人; 以及,
(2) 拿出另一本書,用跟我拿到這本書同樣的方式, 把這另一本書傳出去.
當這本書開始傳出去之後, 第一個拿到書的人, 不用錢就可以讀這本書, 而她/他要做的事情, 就是, 找到一個同意上述規則的人, 把這本書繼續傳出去, 以及拿出另一本書, 作跟最開始傳遞書的人所作一樣的事情。
因此, 一本書傳到第二層時會變成兩本書, 然後是四本, 八本, 十層就是1,024本, 20層就超過1百萬本, 30層呢就是1G本, 40層是1T本。
依據社會科學裡面的小世界理論, 世界上六十億人口通常只需要六個連結就可以連起來, 當這個活動成功地啟動開來時, 我們可能找出一個非預測性的書籍擴散方式, 可以把書籍慢慢地, 但像洪水一樣, 傳遞到社會各個角落, 包括偏遠地區.
而這整個概念, 只要靠活動中的每個人多加入一本書, 以及裡面所蘊藏的遞迴規則來達成. 即使裡面有很多點陣亡或冬眠, 但任何一個節點都可以從新開始, 繼續開展出來.
我們已經開始展開活動了, 現在最需要的就是請大家幫忙把這個概念傳播出去, 更多的內容可參考我們的網站:
http://www.forwardthebook.com
歡迎瞭解這個概念後, 啟動屬於你的遞迴展開式, 也許, 明年的這個時候, 某個偏遠地區的小朋友, 手上讀的書, 就是由你啟動的遞迴展開式所實現的, 而這一切只需要一本書, 一隻原子筆跟一個朋友.
這就是遞迴的力量!
Powerful because of simplicity.
如果每本書可以有追蹤的條碼，譬如每個同意的傳播者統一發給RFID，可能比較容易成功，而不會發生公有地的悲劇。
Dear r2:
有一個活動叫做bookcrossing, 國內版本叫做”行書”, 也是無償放任書去旅行, 在那個活動中, 不可欠缺的核心之一就是, 每本要旅行的書, 得先去申請個unique ID, 透過這個unique ID, 可追蹤書本旅行的軌跡, 而這有賴下一個拿到書的人, 利用這個unique ID到一個中央平台去登錄旅程的最新消息, 經由旅程的更新內容會出現在這個中央平台上, 產生了一股浪漫的動力, 藉此鼓勵人們把心愛的書拿出來, 讓它去參加一場冒險旅行.
bookcrossing是一個很有趣的作法, 不過整個活動的進行有賴一個中央平台, 以提供Unique ID, 以及用以刊載哪些書會放在哪邊, 而這些書又已經經過了多少手的旅程. 而且, 在bookcrossing的活動中, 並沒有要求拿到書的人得再多加入一本書, 拿書的人的義務是, 上網去登錄書的最新行蹤.
幾年前, 國內推動的bookcrossing”行書”, 有很多優秀的菁英參與推動, 當時設計了貼紙, 解決了複雜的資料庫與中文編碼問題, 但後來當中央平台的維護, 出了一些狀況, 立意良好的活動就此停止. 至於國內大塊文化也有在推bookcrossing, 但其撮合平台, 似乎苦於對抗垃圾郵件與色情廣告, 經過初步判讀, 可是成果似乎也是有限.
假如bookcrossing是享受放風箏的快樂, 那麼”把書傳出去”, 就是徹底的放手let go.
你不花錢從一個朋友那邊拿到一本書, 讀完它, 然後把這本書再傳出去, 並且, 拿出另一本書傳出去. 就這樣, 不用複雜的中央平台, 也不需要有甚麼組織號召. 發起人可以完全不懂電腦, 也不需要跟任何人報備. 只要她/他知道這個想法, 有一本書, 一支原子筆, 一個朋友, 傳遞就可以展開. 因此, 即使是鄉下的一個小學生, 只要她/他拿出一本已經看過, 躺在書架很久的注音版小說, 寫上幾行字, 都可以是發起旅程的種子.
是的, 如果沒有RFID的追蹤, 欠缺中央系統的管控, 這些書可能會躺在在某些人的書櫃睡著, 甚至流落到二手書攤. 但書本這種東西不用電池, 有一天也許把這件事忘了十幾年的朋友, 要搬家, 整理書櫃發現, 自己好像忘了遵守一個承諾, 有一天也許有一個在二手書攤翻閱書籍的朋友看到內頁的傳書規則, 這些書本又有機會繼續旅程.
更重要的是, 這個活動當初設計是為了想找出另一種把書傳到偏遠地區的方法. 要解決這個問題, 最根本的一種解決之道就是讓孩子們連上網路, 立刻跟全世界的知識接軌.畢竟, 現在網路上知識爆炸, 就算不看任何需付費的內容, 幾輩子也學不完那麼多東西. 這是為什麼OLPC推出的主要理由, 只要讓偏遠地區的孩子上網, 巨大的改變就有可能產生. 但是, OLPC何時才能一人一台, 又要怎麼樣才能確保一些捐助品不會流入黑市, 就像非洲黑市推滿的紅十字奶粉? 而且, 真的所有孩子都有那麼好的環境可以上網嗎? 如果他們難以上網, 又怎麼存取任何以bookcrossing的中央平台呢?
當然, 有人會說, 現在已經有捐書, 甚至還有到處下鄉的行動圖書館, 與熱血志工. 這些都很棒! 我們想的是, 有沒有可能再多作一些些?
當你“免費”捐書給一個朋友, 這是一件好事. 可是, 如果你不是”免費”提供給這位朋友那本書呢? 這位朋友必須要”還”, 可是不是還回來, 是把它再還出去, 這就是電影”把愛傳出去”(Pay It Forward)的概念. 你不是”免費”接受我的幫助, 你的回報方式是去幫助其他需要幫助的人. 也就是說, “把書傳出去”不是施捨, 可能有些朋友需要等上20年才履行規則的第二個部份, 拿出另一本書傳出去, 可是一旦這位朋友履行時, 這意味著甚麼呢? 我們有了一位願意遵守自己承諾的人, 即使這個承諾看起來多麼的微不足道. 這重不重要? 我們覺得這件事非常重要!
RFID可以建構偉大的監管機制, 可以確保一切都是在秩序下進行, 從追蹤幾萬件包裹橫跨世界五大洲的運送, 到提醒人們記得準時上班不要遲到, 都能發揮重大功效. 是的, 我們相信RFID是個很偉大的發明.
但如果, 我們願意試試看對人們多信任一些呢?
Napster在最開始提出時, 仍然需要一個中央平台用來當作搜尋的中心, 雖然檔案的實際傳輸已經是透過使用者對使用者進行傳遞, 我記得當時有人跟我說, 這就是最大但無法移除的罩門, 因為唱片跟電影業者只要對付這些中心平台就好. 事隔沒多久, 現在的P2P演變成甚麼樣子呢?
“把書傳出去”揉合了bookcrossing, GPL, P2P, Pay It Forward 跟recursive的特徵, 在一切講究快速的年代中, 試著回到一手傳一手的人際接觸, 也許這只是另一個烏托邦的空談而已, 但如果不是呢?
我們正在努力, 想辦法讓這個想法不只是空談, 而你, 也可以幫上忙.
你有一本書, 一支原子筆跟一個可能會想讀這本書的朋友嗎?
參考連結:
http://www.bookcrossing.com
http://en.wikipedia.org/wiki/Bookcrossing
https://www.ylib.com/class/topic/show1.asp?Object=gossip&No=7390
http://vita.fju.edu.tw/vita4/archives/004908.html
http://www.locuspublishing.com/hi/050103_adv.asp
http://www.wretch.cc/blog/pendas&article_id=2375278#comment99762817
http://www.forwardthebook.com/doku.php?id=ftb:priorart
http://en.wikipedia.org/wiki/OLPC
真的很难相信97kb可以做出这么逼真的游戏画面。
曾找过混沌原理的一些书籍来看，但是都不大明白。
我猜97KB的game在CPU的loading會比GPU吃重
因為塞不下那麼多DirectX/OpenGL指令吧
遠古之前, 我還在唸大學的時候也曾經開發過3D game
才發現以前學過的數學原來可以這樣用
(但是發現更多數學沒學好的地方…)
然而當時最大的感觸是: 台灣遊戲如果還是停留在美術/代理的階段, 那永遠都沒有未來的
但是如果要講到台灣遊戲開發的隱憂, 那可能要從Sunday寫到Saturday
只是過了這麼多年, 台灣遊戲還是沒什麼進步啊…
[...] 遞迴之美: 數學, 電腦科學與碎形 [...]