什么是尾递归
如果一个函数在定义时引用了自身，那么这个函数就是一个递归函数。例如我们所熟知的阶乘就可以通过递归函数的形式予以定义
(defun fact (n)
(if (<= n 0)
1
(* n (fact (1- n)))))
在if语句的备选路径上，正在定义的函数fact被自身所调用，因此fact就是一个递归函数了。递归有一类较为特殊的形式，叫做尾递归，它们的特征是递归函数的调用位于被定义函数的最后一个步骤。也就是说，这个递归调用的返回值也就是整个函数调用的返回值，后面不再有其它的计算步骤了。例如实现了辗转相除法的下面这个函数就是尾递归的
(defun my-gcd (a b)
(cond ((zerop a) b)
((zerop b) a)
(t (my-gcd b (mod a b)))))
此处命名为my-gcd，是因为在Common Lisp中已经预置了一个叫做gcd的函数了
什么是尾递归优化
递归调用其实也就是函数调用，每一次调用都需要保存当前的执行上下文（寄存器的值、程序计数器的值等信息）并压入栈中。如果递归调用得非常深，那么很可能将栈空间消耗殆尽导致程序崩溃，因此很多时候都会选择使用循环来实现用递归实现的效果。尾递归形式的一个优势，就在于编译器可以对其进行优化，使得原本需要添加一个栈帧的函数调用操作，直接重用当前的调用中所使用的栈帧即可。这样一来，递归函数的调用就不会无节制地消耗栈空间了。
另一种对尾递归进行优化的方式，则是将其改写为【赋值】与【跳转】。例如对于上面的my-gcd函数，可以改写为如下形式
(defun my-gcd (a b)
(tagbody
rec
(cond ((zerop a) (return-from my-gcd b))
((zerop b) (return-from my-gcd a))
(t (progn
(psetf a b
b (mod a b))
(go rec))))))
如何在Common Lisp中实现
如果要使用递归的形式定义一个计算列表长度的函数，那么很可能会写出这样子的代码
(defun my-length (lst)
(if (null lst)
0
(1+ (my-length (rest lst)))))
采用累加器的思路，可以将上述函数改写为下面的尾递归形式
(defun my-length (lst acc)
(if (null lst)
acc
(my-length (rest lst) (1+ acc))))
对于第二个版本的my-length函数，同样可以手动改写为基于【赋值】和【跳转】的实现形式，结果如下
(defun my-length (lst acc)
(tagbody
rec
(if (null lst)
(return-from my-length acc)
(progn
(psetf lst (rest lst)
acc (1+ acc))
(go rec)))))
你可能已经注意到了，my-gcd和my-length函数的改写都是很有规律的，甚至可以通过一个宏来帮助我们自动完成这种变换。这个宏所需要做的事情其实只有三件：
- 将原本的定义中的函数体包裹在一个
tagbody中 - 将原本作为返回值的表达式包裹在一个
return-from中 - 将递归调用的表达式改为按顺序执行的
psetf和go的组合
为了降低一下实现难度，第二点暂时就不处理了，函数的实现者必须手动编写return-from语句。因此，如果只考虑首尾两个条件，首先，可以考虑实现第三条，将函数体内的递归调用修改为progn、psetf和go的组合。要实现这个变换，可以使用macrolet，如下
(defun my-length (lst acc)
(tagbody
rec
(macrolet ((my-length (&rest args)
`(progn
(psetf ,@(mapcan #'list '(lst acc) args))
(go rec))))
(if (null lst)
(return-from my-length acc)
(my-length (rest lst) (1+ acc))))))
为了自动生成上面的代码，我编写了这样的一个宏
(defmacro define-rec (name lambda-list &body body)
(let ((rec (gensym)))
`(defun ,name ,lambda-list
(tagbody
,rec
(macrolet ((,name (&rest exprs)
,``(progn
(psetf ,@(mapcan #'list ',lambda-list exprs))
(go ,',rec))))
,@body)))))
利用上面这个宏编写一个计算列表长度的尾递归形式的函数，代码如下
(define-rec my-length (lst acc)
(if (null lst)
(return-from my-length acc)
(my-length (rest lst) (1+ acc))))
利用macroexpand-1或者是SLIME提供的展开一次宏的调试功能，在我的机器上得到的代码如下
(DEFUN MY-LENGTH (LST ACC)
(TAGBODY
#:G937
(MACROLET ((MY-LENGTH (&REST EXPRS)
`(PROGN
(PSETF ,@(MAPCAN #'LIST '(LST ACC) EXPRS))
(GO ,'#:G937))))
(IF (NULL LST)
(RETURN-FROM MY-LENGTH ACC)
(MY-LENGTH (REST LST) (1+ ACC))))))
跟上面手写的代码没有太大的差别，并且用于计算所得到的列表长度也是正确的。那么如何验证这个函数是采用了【赋值】和【跳转】的机制来完成运算的呢？可以借助Common Lisp提供的trace函数。如果使用的真实执行递归调用的my-length函数的定义，那么执行(trace my-length)后运行(my-length '(1 2 4 5) 0)，在我的机器上会输出如下内容
CL-USER> (my-length '(1 2 4 5) 0)
0: (MY-LENGTH (1 2 4 5) 0)
1: (MY-LENGTH (2 4 5) 1)
2: (MY-LENGTH (4 5) 2)
3: (MY-LENGTH (5) 3)
4: (MY-LENGTH NIL 4)
4: MY-LENGTH returned 4
3: MY-LENGTH returned 4
2: MY-LENGTH returned 4
1: MY-LENGTH returned 4
0: MY-LENGTH returned 4
4
而如果是使用define-rec宏定义的my-length，求值同样的表达式的输出为
CL-USER> (my-length '(1 2 4 5) 0)
0: (MY-LENGTH (1 2 4 5) 0)
0: MY-LENGTH returned 4
4
显然，这当中没有递归的函数调用，my-length确实不需要调用自身。
全文完
网友评论