百度百科对尾递归的解释是这样的,“如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。” 并且,特别强调了两点,1)递归调用是函数体最后执行的语句,2)递归调用的返回值不属于表达式的一部分,也就是说, 递归调用的返回值不参与最后一条语句的求值,递归调用仅仅是为了进入下一个迭代。

语言表达起来可能比较生硬晦涩,上一段代码举例也许就比较形象了。

lisp语言的大多数实现,都内置了一个名为reverse的函数,其功能是将list中的元素颠倒。如果要自行实现这个函数, 可以用递归的形式写作下面这样子:

1
2
3
4
(defun xg/reverse (lst) 
  (if (null lst) 
    '()
    (append (xg/reverse (cdr lst)) (list (car lst)))))

不难看出,递归调用也算是出现在上述代码的函数末尾,只是它并非函数体最后执行的语句,最后执行的语句是append, 并且,递归调用的返回值也参与了最后语句的求值,因此,上面这段代码并非是尾递归的。

如果要做到递归调用的返回值不参与求值,那么就只能通过引入变量(形参)来保存递归过程中的中间值了,这样就做到了尾递归了。 上述代码的尾递归版本,可以写作下面这样:

1
2
3
4
5
6
(defun xg/reverse2 (lst / _myrev) 
  (defun _myrev (lst tmp) 
    (if (null lst) 
      tmp
      (_myrev (cdr lst) (cons (car lst) tmp))))
  (_myrev lst nil))

_myrev函数中,引入了tmp这个形参来保存递归过程中的中间值,在达到递归终止条件后,再将这个形参的值作为最终结果返回。 这样,就实现了一个尾递归版的reverse函数了。