Contents
简介
尾递归是一种特殊的递归形式,可以很容易地被转化成迭代形式。当调用一个函 数的时候,计算机必须记住他是从哪里被调用的,这样才能在调用完成之后回到 原来的那个地方,这样的信息通常被保存在栈上面。
但是,有时候一个函数在完成了所有必须的工作之后,最后一件事情就是调用一 个函数(有可能是他自己),并返回得到的结果,这种情况下就没有必要在调用完 成之后再跳转回来,也就不需要记住返回地址,只需要让新调用的函数直接把结 果返回到最初的调用者那里就可以了。像这样把一个函数调用转化为一个分支或 跳转的方法就叫做 尾递归优化 。
值得注意的是,这里的“最后一件事情”并不是字面上的“函数的最后一条语句”一 类的,只要在调用函数之后结果立即被返回,而不会再做其他任何处理,就是一 个尾递归。
一个例子
作为一个例子,我们来看一个用 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 语言写的拷贝链表的函数:
可以被转化为这样的尾递归:
从而最终通过尾递归优化而被编译器转化为迭代形式: