张大胖学递归

算法与数据结构 · 公众号 · 算法 · 2016-11-29 09:27

正文

来自：码农翻身（微信号：coderising）

作者：刘欣

张大胖上数据结构课，老师讲汉诺塔问题，使用了递归算法。

张大胖第一次接触递归，一头雾水，想破了脑袋也没搞明白这递归是怎么回事，他一直很纳闷，这么复杂的问题，怎么可能就那么两三行代码就解决了？这怎么可能？

后来经好基友Bill指点，总算明白一点，但总是觉得还有点疑虑，不太敢确信自己是不是真的搞明白了。

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

Bill一边说，一遍写下了下面的代码：

“看看，是不是特别简单，所谓递归，就是一个函数调用了自己而已！”

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

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

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

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

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

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

Bill说：“注意看堆栈中的栈帧啊， 每个栈帧就代表了被调用中的一个函数 ，这些函数栈帧以先进后出的方式排列起来，就形成了一个栈，拿放大镜栈帧放大来看就是这样：”

（码农翻身注：返回值有时候用寄存器传递，这里是为了展示阶乘的例子，特意把返回值画上了）

"如果我们忽略到其他内容，只关注输入参数和返回值的话，我们的阶乘函数factorial（4）会是这样" Bill接着又画了起来。

（码农翻身注：栈顶在下边）

张大胖说：“明白了，原来计算机是这么处理函数调用的啊，在计算factorial(4)的时候，方法是

4 *factorial(3) ，现在4的值有了，但是factorial(3) 的值还不知道是多少，所以就需要形成新的栈帧来计算，而factorial(3) 需要 factorial(2)， factorial(2) 需要 factorial(1)，如果循环，不，是递归下去，到最后才能得到 factorial(1) = 1，然后每个栈帧逐次出栈，就能计算出最终的factorial(4)了”