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

收敛的递归

好了, 这些无限递归可能让你有点烦闷了, 让我们看点会收敛的:

你是否想起了这样的诗句:

你站在桥上看风景

看风景的人在楼上看你

明月装饰了你的窗子

你装饰了别人的梦

–卞之琳<<断章>>

再来看看据说是 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 元的组合总共有几种), 从中可以体现递归的优势.

由于篇幅有限, 这些将在后续篇章中谈及.

原文地址：https://blog.csdn.net/ShawGolden/article/details/140174198

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！