有趣的遞歸(Recursion)，一些直觀的示例

從前有座山，山上有座廟，廟里有個老和尚在給小和尚講故事：“從前有座山，山上有座廟，廟里有個老和尚在給小和尚講故事：……”

反復而糾結的定義

看完這個故事，對遞歸你已經有了印象，很好，這樣已足夠。如果你不幸是個喜歡精確定義的人，那么答案可能無法讓你滿意：

你想知道遞歸是什么，你得先知道什么是遞歸。To understand recursion, you must understand recursion.

把你繞暈了沒有？你可能想這叫啥子定義喲。如果你去谷歌英文頁搜索“recursion”，谷歌就會給你來這么一下：

谷歌說：“你是說遞歸嗎？(Did you mean: recursion)”。

拼寫絕對是正確的，這不過是谷歌給你開的“遞歸式”的玩笑。

說完了谷歌，再說說必應（Bing），Bing是什么意思呢：

Bing = Bing is not google（Bing不是谷歌）

你還是不滿意，那再看看GNU，GNU又是啥呢：

GNU = GNU’s Not Unix（GNU不是Unix）

收斂的遞歸

好了，這些無限遞歸可能讓你有點煩悶了，讓我們看點會收斂的（圖片來自google圖片搜索）：

你是否想起了這樣的詩句：

你站在橋上看風景，看風景的人在樓上看你。明月裝飾了你的窗子，你裝飾了別人的夢。——卞之琳《斷章》

再來看看據說是MIT計算機系的徽標：

MIT：MASSACHUSETTS INSTITUTE OF TECHNOLOGY 麻省理工學院（麻省：即馬薩諸塞州）

圖上有個lambda（λ），至于那個(Y F)=(F (Y F))，有沒有哪頭技術大奶牛知道它是啥呢？

不太清楚這玩意是啥~但公式可參見：http://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combinator

另可參考mindhacks.cn上的這篇康托爾、哥德爾、圖靈——永恒的金色對角線(rev#2)（沒怎么看懂~有興趣有精力的同學可鉆研看看。）

自相似性（self-similarity）

下面是一顆自然界的完全二叉樹（A complete binary tree in nature，來自http://www.cs.haifa.ac.il/~shlomit/，作者攝于非洲）

下圖為芒德布羅集（Mandelbrot set），是分形（Fractal）理論中的一個概念：

這個圖很好體現了一種自相似性，實際上，不斷放大這個圖會發現模式在不斷重復。

來自優酷的這個視頻展示了這一點：http://v.youku.com/v_show/id_XMTc3NzIyMjI0.html

內容來自數學科教影片http://www.dimensions-math.org/Dim_ZH_si.htm（如果你有興趣，還有另一部http://www.chaos-math.org/zh-hans）

其它示例

艾舍爾版畫（來自http://www.guokr.com/blog/50805/）

這里的艾舍爾就是那本《哥德爾、艾舍爾、巴赫——集異璧之大成》（G?del, Escher, Bach: an Eternal Golden Braid）中的艾舍爾了。見http://book.douban.com/subject/1291204/

我發現此書英文版居然早在1979年就出版了，作者Douglas Hofstadter還取了個中文名叫“侯世達”。

下圖則為電影《盜夢空間》（Inception）中的一幕（其實這種場景在理發店也很常見~）：

電影情節中的夢中夢也頗有遞歸的意味。

制造遞歸

如果你有個可移動的攝像頭，讓屏幕上播放攝像頭實時拍攝的畫面，然后拿著攝像頭對準屏幕，就能得到類似下圖中的效果：

你可以想想，為什么會這樣呢？

與此相似的一個例子是音箱的爆音，在一些會場，有時會不小心把麥克風對誰了音箱，大功率音箱一開始存在一些很小的電流聲，這些聲音被麥克風捕獲又傳入音箱再次放大又傳到麥克風上……很快就會演變成刺耳的尖銳聲。

程序中的遞歸

文件夾的遞歸結構：

所以，用遞歸去處理這些是很常見的情形。類似的還包括那些有著樹形結構特點的如XML，HTML

以及Chrome瀏覽器中window對象的自指遞歸：

window對象是javascript在瀏覽器端的擴展中的全局對象（類似node.js中的global），它里面又包含了一個名為“window”的屬性指向它自身，所以可以像上圖那樣無限展開。（遍歷處理這種結構需要特別小心，否則很可能會收到stack overflow的錯誤~）

以上談了不少的例子，都沒有涉及具體的編程，是想讓大家對遞歸有一個直觀的印象先，后面會談到一些經典的例子，如階乘以及菲波那契數列，還有用遞歸來做排序（如簡單的冒泡排序），最后將展示一個用遞歸方式來計算換零錢種數的例子（比如用100元，換成50，20，10，5，1元的組合總共有幾種），從中可以體現遞歸的優勢。由于篇幅有限，這些將在后續篇章中談及。

來自：http://my.oschina.net/goldenshaw/blog/356887