什么是尾递归

这一篇主要是因为在饭否上看到一条消息：

@量子小熊: 每个声称自己会Scala的，我都让他写尾递归的List反转，目前还没有一个写出来的，知道啥是尾递归的都是稀有动物。

吓得我赶快复习了一下尾递归（可惜并不会Scala）。怎么说也是SICP从入门到放弃的人，不懂这个实在不像话（讲尾递归的在第23页，中文版）。

迭代

经常和递归混淆的一个词是迭代(iteration)。迭代是指对某一过程的重复。比如for循环之类的，就可以看作是迭代的过程。实际上迭代和尾递归有很深的联系。

比如算一个阶乘

x = 1
for i in range(1, 7):
    x *= i

递归

那么，什么是递归(recursion)？简单理解的话，就是一个函数在执行自己的过程中又调用了自己，从而形成反复调用自己的效果。

递归有什么用呢？嗯...当你使用一门没有for循环的语言时(???)，就可以用递归来模拟一下for循环。好吧，其实递归是个很常用的东西。例如在操作二叉树之类的数据结构时，都会用到递归（当然它本身也是一种递归定义的数据结构）。

在函数执行的时候，会有一个局部的环境，栈帧，里面存放了函数的局部变量，返回地址之类的东西。当一个函数进行递归的时候，会不断重复产生新的栈帧，多到一定程度就stack overflow了。

我们使用Python写代码时，当递归次数多了，解释器会报RuntimeError: maximum recursion depth exceeded，是因为Python限制了最大递归深度，不允许无限大的递归。

比如算一个阶乘

def factorial(x):
    if x == 1:
        return x
    return x * factorial(x-1)

factorial(6)

尾递归

那么什么是尾递归（tail recursion）呢？首先它是一个递归。然后，它和普通递归的区别在于，它是在最后一步调用了自己并直接把其返回值直接返回。（敢不敢再绕一点）

这就意味着需要的数据已经都丢给尾部调用的那个函数了，不会对后者的返回值做其他处理，因此可以复用当前栈帧，以节约内存空间。这样就实现了能够使用恒定的内存空间执行递归。（实际上相当于迭代）

尾递归的目的在于，用一个递归过程，达到迭代计算过程的效果。

比如算一个阶乘（可以与上面的普通递归版比较一下区别）

def factorial(result, n):
    if n == 1:
        return result
    result *= n
    return factorial(result, n-1)

factorial(1, 6)

尾递归优化

伴随着尾递归来的还有一个概念，叫作尾递归优化（Tail Call Optimization, TCO）

有的编译器，比如Scheme，会做一些微小的工作对尾递归进行优化。也只有在支持尾递归优化的语言中才可以玩尾递归，不然就算写成了尾递归也是不会有任何效果的，依然会随着递归次数的增加不断消耗内存（例如Python就不行，所以上面写的那个虽然是尾递归的形式，但并没有得到优化）

这些编译器会在编译时把递归过程优化为迭代的过程，也就是上面说的复用栈帧，节约内存空间。

有了一个尾递归的实现，我们就可以利用常规的过程调用机制表述迭代，这也会使各种复杂的专用迭代结构变成不过是一些语法糖衣了。 —— SICP 1.2

总的来说，这是一个比较tricky的东西，在写项目的时候，就算语言支持尾递归优化，能常规迭代写完的东西就不要尾递归了，代码的可维护性也是比较重要的（乱写的话，极有可能被人打死）=。=