|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
小不二上数据结构课， 老师讲汉诺塔问题， 使用了递归算法。
小不二第一次接触递归， 一头雾水，想破了脑袋也没搞明白这递归是怎么回事。
他 一直很纳闷， 这么复杂的问题， 怎么可能就那么两三行代码就解决了？
这怎么可能？
后来经好基友小甲鱼老湿指点， 总算明白一点！
但总是觉得还有点疑虑，不太敢确信自己是不是真的搞明白了。
小甲鱼老湿说： “给你来个简单点儿的例子，计算n的阶乘， 这个描述起来更直接”
小甲鱼老湿一边说，一遍写下了下面的代码：
“看看， 是不是特别简单。“
”所谓递归，就是一个函数调用了自己而已！”
“一个调用自己的函数， 这听起来就有点匪夷所思了” 小不二感慨到。
“其实没那么复杂， 你就假想着调用了另外一个函数， 只不过这个函数的代码和上一个一模一样而已。”
“我们人不会这么做事情， 但是这是个程序， 它在机器层面到底是怎么执行的？ ” 小不二问道。
小甲鱼老湿 说 “ 我给你画个图， 一个程序在内存中逻辑上看起来像这个样子”
“就拿我们的阶乘函数来说吧， 编译后会被放到代码段， 注意， 只有一套代码放在代码段。 ”
小不二说： “只有一套代码， 那怎么实现自己调用自己的所谓递归啊？ ”
小甲鱼老湿说：“注意看堆栈中的栈帧啊， 每个栈帧就代表了被调用中的一个函数。
这些函数栈帧以先进后出的方式排列起来，就形成了一个栈， 拿放大镜栈帧放大来看就是这样：”
（返回值有时候用寄存器传递， 这里是为了展示阶乘的例子，特意把返回值画上了）
"如果我们忽略到其他内容， 只关注输入参数和返回值的话， 我们的阶乘函数factorial（4）会是这样"
小甲鱼老湿接着又画了起来。
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2016-11-29 14:31:21
置顶卡
千斤顶
显身卡
发表于 2016-11-29 21:20:36
楼主
发表于 2017-9-16 09:53:36