张大胖学递归

张大胖上数据结构课， 老师讲汉诺塔问题， 使用了递归算法。
张大胖第一次接触递归， 一头雾水，想破了脑袋也没搞明白这递归是怎么回事， 他 一直很纳闷， 这么复杂的问题， 怎么可能就那么两三行代码就解决了？  这怎么可能？

后来经好基友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)了”

(点击看大图)

"注意， 每个递归函数必须得有个终止条件， 要不然就会发生无限递归了， 永远都出不来了。"
张大胖又问 ：”这个堆栈容量也是有限的吧， 如果n的值太大了， 是不是有可能爆掉？“
“是啊，每个栈帧都需要占用空间， 维护这些栈也挺费劲， 递归层次太深就会出问题。 ”
“那怎么办？  这种函数的调用关系，好像只能这样了。 ”
“这是由我们的算法决定的， factorial(n) = n * factorial(n-1 )  ,  所以之前的图中每个栈帧都需要记录下当前的n 的值， 还要记录下一个函数栈帧的返回值， 然后才能运算出当前栈帧的结果。 也就是说使用多个栈帧是不可避免的。 不过我们改下递归算法就有救了”

"这个方法看起来有点古怪啊， 还多传递了一个参数过来"
Bill说： ”不仅仅多了一个参数， 注意函数的最后一个语句， 就不是 n * factorial(n-1) 了， 而是直接调用factorial(....) 这个函数本身，  这就带来了巨大的好处。 ”
张大胖说：“不懂”
“你看看这个新算法的计算过程：”

“当你执行到factorial(1, 24)的时候， 还需要退回到factorial(2, xxx)这个函数吗？”
张大胖说：“看来不需要， 直接就可以返回结果了。”
“这就是妙处所在了， 计算机发现这种情况， 只用一个栈帧就可以搞定这些计算， 无论你的n 有多大。”

大胖感慨到： “果然是， 同一个栈帧，完全可以在递归中被复用啊， n 无论多大都不怕了。 ”
“这种方式就是我们常说的尾递归了， 当递归调用是函数体中最后执行的语句并且它的返回值不属于表达式一部分时， 这个递归就是尾递归。
现代的编译器就会发现这个特点， 生成优化的代码， 复用栈帧。  第一个算法中因为有个n * factorial(n-1) ,  虽然也是递归， 但是递归的结果处于一个表达式中， 还要做计算， 所以就没法复用栈帧了， 只能一层一层的调用下去。 ”
“看来理解了计算机机器层面的东西才能更好的理解啊”
“没错， 计算机的基础非常重要。”

（完）

你看到的只是冰山一角， 更多精彩文章，尽在“码农翻身” 微信公众号， 回复消息"m"或"目录" 查看更多文章
有心得想和大家分享？ 欢迎投稿 ！ 我的联系方式：微信：liuxinlehan  QQ: 3340792577

公众号：码农翻身“码农翻身”公众号由工作15年的前IBM架构师创建，分享编程和职场的经验教训。

掘金是一个高质量的技术社区，从 Swift 到 React Native，性能优化到开源类库，让你不错过互联网开发的每一个技术干货。长按图片二维码识别或者各大应用市场搜索「掘金」，技术干货尽在掌握中。