有趣的递归(Recursion),一些直观的示例

摘要:递归的一些有趣例子。

目录
[隐藏]

从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事:“从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事:……”

反复而纠结的定义

看完这个故事,对递归你已经有了印象,很好,这样已足够。如果你不幸是个喜欢精确定义的人,那么答案可能无法让你满意:

你想知道递归是什么,你得先知道什么是递归。To understand recursion, you must understand recursion.

把你绕晕了没有?你可能想这叫啥子定义哟。如果你去谷歌英文页搜索“recursion”,谷歌就会给你来这么一下:

image

谷歌说:“你是说递归吗?(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/,作者摄于非洲)

image

下图为芒德布罗集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/

image

这里的艾舍尔就是那本《哥德尔、艾舍尔、巴赫——集异璧之大成》(Gödel, Escher, Bach: an Eternal Golden Braid)中的艾舍尔了。见http://book.douban.com/subject/1291204/

我发现此书英文版居然早在 1979 年就出版了,作者 Douglas Hofstadter 还取了个中文名叫“侯世达”。

下图则为电影《盗梦空间》(Inception)中的一幕(其实这种场景在理发店也很常见~):

image

电影情节中的梦中梦也颇有递归的意味。

制造递归

如果你有个可移动的摄像头,让屏幕上播放摄像头实时拍摄的画面,然后拿着摄像头对准屏幕,就能得到类似下图中的效果:

image

你可以想想,为什么会这样呢?

与此相似的一个例子是音箱的爆音,在一些会场,有时会不小心把麦克风对谁了音箱,大功率音箱一开始存在一些很小的电流声,这些声音被麦克风捕获又传入音箱再次放大又传到麦克风上……很快就会演变成刺耳的尖锐声。

程序中的递归

文件夹的递归结构:

image

所以,用递归去处理这些是很常见的情形。类似的还包括那些有着树形结构特点的如 XML,HTML

以及 Chrome 浏览器中 window 对象的自指递归:

image

window 对象是 javascript 在浏览器端的扩展中的全局对象(类似  node.js 中的 global),它里面又包含了一个名为“window”的属性指向它自身,所以可以像上图那样无限展开。(遍历处理这种结构需要特别小心,否则很可能会收到 stack overflow 的错误~)

以上谈了不少的例子,都没有涉及具体的编程,是想让大家对递归有一个直观的印象先,后面会谈到一些经典的例子,如阶乘以及菲波那契数列,还有用递归来做排序(如简单的冒泡排序),最后将展示一个用递归方式来计算换零钱种数的例子(比如用 100 元,换成 50,20,10,5,1 元的组合总共有几种),从中可以体现递归的优势。由于篇幅有限,这些将在后续篇章中谈及。

发表评论

电子邮件地址不会被公开。 必填项已用*标注