#递归 - 深度解析【小甲鱼友情客串】

不二如是

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

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

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

这怎么可能？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

万花凋落尽

111





嘿，亲爱的鱼油，每天都要过得开心哦^_^

a1437485261

111111

FC10086

see