Question

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

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

大胖感慨到： “果然是， 同一个栈帧，完全可以在递归中被复用啊， n 无论多大都不怕了。 ”

“这种方式就是我们常说的 尾递归 了， 当递归调用是函数体中最后执行的语句并且它的返回值不属于表达式一部分时， 这个递归就是尾递归。

现代的编译器就会发现这个特点， 生成优化的代码， 复用栈帧。 第一个算法中因为有个 n * factorial(n-1) , 虽然也是递归， 但是递归的结果处于一个表达式中， 还要做计算， 所以就没法复用栈帧了， 只能一层一层的调用下去。 ”

“看来理解了计算机机器层面的东西才能更好的理解啊”

“没错， 计算机的基础非常重要。”