鱼C论坛

 找回密码
 立即注册
查看: 3027|回复: 3

[好文转载] #递归 - 深度解析【小甲鱼友情客串】

[复制链接]
发表于 2016-11-29 14:35:12 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 不二如是 于 2016-11-29 14:44 编辑

小不二上数据结构课, 老师讲汉诺塔问题, 使用了递归算法。

小不二第一次接触递归, 一头雾水,想破了脑袋也没搞明白这递归是怎么回事。

他 一直很纳闷, 这么复杂的问题, 怎么可能就那么两三行代码就解决了?  

这怎么可能?

0.png


后来经好基友小甲鱼老湿指点, 总算明白一点!

但总是觉得还有点疑虑,不太敢确信自己是不是真的搞明白了。

小甲鱼老湿说: “给你来个简单点儿的例子,计算n的阶乘, 这个描述起来更直接”

小甲鱼老湿一边说,一遍写下了下面的代码:

1.png


“看看, 是不是特别简单。“

”所谓递归,就是一个函数调用了自己而已!”

“一个调用自己的函数, 这听起来就有点匪夷所思了” 小不二感慨到。

“其实没那么复杂, 你就假想着调用了另外一个函数, 只不过这个函数的代码和上一个一模一样而已。”

“我们人不会这么做事情,  但是这是个程序, 它在机器层面到底是怎么执行的? ” 小不二问道。

小甲鱼老湿 说  “ 我给你画个图, 一个程序在内存中逻辑上看起来像这个样子”

2.png


“就拿我们的阶乘函数来说吧, 编译后会被放到代码段, 注意, 只有一套代码放在代码段。

小不二说: “只有一套代码, 那怎么实现自己调用自己的所谓递归啊? ”

小甲鱼老湿说:“注意看堆栈中的栈帧啊, 每个栈帧就代表了被调用中的一个函数。

这些函数栈帧以先进后出的方式排列起来,就形成了一个栈, 拿放大镜栈帧放大来看就是这样:”
(返回值有时候用寄存器传递, 这里是为了展示阶乘的例子,特意把返回值画上了)

3.png


游客,如果您要查看本帖隐藏内容请回复
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-9-21 11:56:09 | 显示全部楼层
111





嘿,亲爱的鱼油,每天都要过得开心哦^_^
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-6-4 20:59:12 | 显示全部楼层
111111
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-10-9 11:44:10 | 显示全部楼层
see
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 19:38

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表