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

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

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

迭代

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

比如算一个阶乘

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

递归

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

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的东西,在写项目的时候,就算语言支持尾递归优化,能常规迭代写完的东西就不要尾递归了,代码的可维护性也是比较重要的(乱写的话,极有可能被人打死)=。=