Tail Recursion

简介

尾递归是一种特殊的递归形式,可以很容易地被转化成迭代形式。当调用一个函 数的时候,计算机必须记住他是从哪里被调用的,这样才能在调用完成之后回到 原来的那个地方,这样的信息通常被保存在栈上面。

但是,有时候一个函数在完成了所有必须的工作之后,最后一件事情就是调用一 个函数(有可能是他自己),并返回得到的结果,这种情况下就没有必要在调用完 成之后再跳转回来,也就不需要记住返回地址,只需要让新调用的函数直接把结 果返回到最初的调用者那里就可以了。像这样把一个函数调用转化为一个分支或 跳转的方法就叫做 尾递归优化

值得注意的是,这里的“最后一件事情”并不是字面上的“函数的最后一条语句”一 类的,只要在调用函数之后结果立即被返回,而不会再做其他任何处理,就是一 个尾递归。

一个例子

作为一个例子,我们来看一个用 Common Lisp 实现的求阶乘的例子,首先是一 个非尾递归的形式:

看一下 TRACE 的结果:

这个并不是尾递归,因为在调用了 (factorial (1- n)) 之后,他还要进行将结 果乘以 n 的处理。不过这样的函数可以通过加上一个 accumulator 轻易将起转 化为尾递归:

不过这个把 iterate 定义在 factorial-tail-recursion 内部了,我们 TRACE 的话只能看到他一步就返回了,所以我们干脆把 iterate 定义为一个全 局的函数,把他也 TRACE 上:

可以看到,后面一直都是返回 6 ,也就是说,把上一次汉度调用的结果直接返 回而没有进行任何处理。这种尾递归可以轻易地被编译器或者手工转化为迭代形 式:

事实上,递归形式的代码通常简洁而且结构清晰(这里的例子只是因为太简单了, 所以没有看出什么明显的优势),但普通的递归调用通常会比较低效,所以尾递归 通常受到人们的青睐,特别是在函数式编程的领域,在 Scheme 里面甚至将尾递 归优化作为语言的一个标准。

Tail recursion modulo cons

这是由 David H.D. Warren 引进的尾递归的一种推广,如果在递归调用之后唯 一需要做的一件事情只有一个 cons ,即把一个元素加到返回的列表里面,那么 这就是一个 tail recursion modulo cons 。这可以通过创建节点,再把他的引 用作为参数传递来实现优化,以转化为一个尾递归。这里有一个来自于 Wikipedia 的例子,用 C 语言写的拷贝链表的函数:

可以被转化为这样的尾递归:

从而最终通过尾递归优化而被编译器转化为迭代形式: