有趣的递归(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