#递归 - 深度解析【小甲鱼友情客串】
小不二上数据结构课， 老师讲汉诺塔问题， 使用了递归算法。小不二第一次接触递归， 一头雾水，想破了脑袋也没搞明白这递归是怎么回事。
他 一直很纳闷， 这么复杂的问题， 怎么可能就那么两三行代码就解决了？
这怎么可能？
后来经好基友小甲鱼老湿指点， 总算明白一点！
但总是觉得还有点疑虑，不太敢确信自己是不是真的搞明白了。
小甲鱼老湿说： “给你来个简单点儿的例子，计算n的阶乘， 这个描述起来更直接”
小甲鱼老湿一边说，一遍写下了下面的代码：
“看看， 是不是特别简单。“
”所谓递归，就是一个函数调用了自己而已！”
“一个调用自己的函数， 这听起来就有点匪夷所思了” 小不二感慨到。
“其实没那么复杂， 你就假想着调用了另外一个函数， 只不过这个函数的代码和上一个一模一样而已。”
“我们人不会这么做事情，但是这是个程序， 它在机器层面到底是怎么执行的？ ” 小不二问道。
小甲鱼老湿 说“ 我给你画个图， 一个程序在内存中逻辑上看起来像这个样子”
“就拿我们的阶乘函数来说吧， 编译后会被放到代码段， 注意， 只有一套代码放在代码段。 ”
小不二说： “只有一套代码， 那怎么实现自己调用自己的所谓递归啊？ ”
小甲鱼老湿说：“注意看堆栈中的栈帧啊， 每个栈帧就代表了被调用中的一个函数。
这些函数栈帧以先进后出的方式排列起来，就形成了一个栈， 拿放大镜栈帧放大来看就是这样：”
（返回值有时候用寄存器传递， 这里是为了展示阶乘的例子，特意把返回值画上了）
"如果我们忽略到其他内容， 只关注输入参数和返回值的话， 我们的阶乘函数factorial（4）会是这样"
小甲鱼老湿接着又画了起来。
**** Hidden Message *****
谢谢楼主 本帖最后由 四十二 于 2016-11-30 12:37 编辑
强势围观！！！
to iterate is human，to recurse divine 非官方认证 发表于 2016-11-29 21:20
谢谢楼主
{:10_303:} 四十二 发表于 2016-11-29 22:04
强势围观！！！
to iterate is human，to recurse is divine
好一个
to iterate is human
to recurse is divine 学习 学习一下。。。 kankanba good very much\
领教 很好的文章，值得学习 很有收获 学习使人进步 11
学习中 受教了
页:
[1]