QQ登录

只需一步,快速开始

登录 | 立即注册 | 找回密码

主题

帖子

荣誉

管理团队

Rank: 30Rank: 30Rank: 30Rank: 30

技术值
查看: 481|回复: 14

[技术交流] #递归 - 深度解析【小甲鱼友情客串】

[复制链接]
最佳答案
96 
累计签到:478 天
连续签到:6 天
不二如是 发表于 2016-11-29 14:31:21 48114 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

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

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

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

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

这怎么可能?

0.png


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

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

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

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

1.png


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

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

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

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

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

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

2.png


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

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

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

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

3.png


"如果我们忽略到其他内容, 只关注输入参数和返回值的话, 我们的阶乘函数factorial(4)会是这样"

小甲鱼老湿接着又画了起来。

游客,如果您要查看本帖隐藏内容请回复

楼层
跳转到指定楼层
最佳答案
0 
累计签到:132 天
连续签到:1 天
非官方认证 发表于 2016-11-29 21:20:36 | 显示全部楼层
谢谢楼主
最佳答案
1 
累计签到:101 天
连续签到:1 天
四十二 发表于 2016-11-29 22:04:30 | 显示全部楼层
本帖最后由 四十二 于 2016-11-30 12:37 编辑

强势围观!!!

to iterate is human,to recurse divine
最佳答案
96 
累计签到:478 天
连续签到:6 天
不二如是  楼主| 发表于 2016-11-30 05:59:23 | 显示全部楼层
最佳答案
96 
累计签到:478 天
连续签到:6 天
不二如是  楼主| 发表于 2016-11-30 06:00:45 | 显示全部楼层
四十二 发表于 2016-11-29 22:04
强势围观!!!

to iterate is human,to recurse is divine

好一个
to iterate is human

to recurse is divine
最佳答案
0 

尚未签到

llqh540 发表于 2017-3-12 15:50:17 | 显示全部楼层
学习
最佳答案
0 
累计签到:196 天
连续签到:1 天
heidi620 发表于 2017-3-16 20:25:35 | 显示全部楼层
学习一下。。。
最佳答案
0 
累计签到:62 天
连续签到:1 天
大江流 发表于 2017-3-16 23:47:06 | 显示全部楼层
kankanba good very much\
最佳答案
1 
累计签到:79 天
连续签到:1 天
jdp7385 发表于 2017-3-17 08:41:54 From FishC Mobile | 显示全部楼层
领教
最佳答案
0 
累计签到:17 天
连续签到:1 天
天涯浪人 发表于 2017-3-17 15:53:05 | 显示全部楼层
很好的文章,值得学习
最佳答案
0 
累计签到:2 天
连续签到:1 天
操琴弓的魔术师 发表于 2017-9-14 15:06:13 From FishC Mobile | 显示全部楼层
很有收获
最佳答案
0 
累计签到:2 天
连续签到:2 天
sp1ral 发表于 2017-9-16 09:53:36 From FishC Mobile | 显示全部楼层
学习使人进步
最佳答案
0 

尚未签到

11温柔 发表于 2017-9-18 11:23:14 | 显示全部楼层
11
最佳答案
0 
累计签到:10 天
连续签到:1 天
tankefu 发表于 2017-9-18 23:52:19 From FishC Mobile | 显示全部楼层
学习中
最佳答案
0 
累计签到:1 天
连续签到:1 天
verygoodbook 发表于 2017-9-21 02:15:41 | 显示全部楼层
受教了

发表回复

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

本版积分规则

关闭

小甲鱼强烈推荐 上一条 /1 下一条

    移动客户端下载(未启用)
    微信公众号

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备11014136号

Copyright 2018 鱼C论坛 版权所有 All Rights Reserved.

Powered by Discuz! X3.1 Copyright
© 2001-2018 Comsenz Inc.    All Rights Reserved.

小黑屋|手机版|Archiver|鱼C工作室 ( 粤公网安备 44051102000370号 | 粤ICP备11014136号

GMT+8, 2017-11-24 23:00

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