Tail Recursion

Contents

简介
一个例子
Tail recursion modulo cons

简介

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

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

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

一个例子

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

(defun factorial (n)
  (if (= n 0)
      1
      (* n (factorial (1- n)))))

看一下 TRACE 的结果：

CL-USER> (trace factorial)
(FACTORIAL)
CL-USER> (factorial 3)
  0: (FACTORIAL 3)
    1: (FACTORIAL 2)
      2: (FACTORIAL 1)
        3: (FACTORIAL 0)
        3: FACTORIAL returned 1
      2: FACTORIAL returned 1
    1: FACTORIAL returned 2
  0: FACTORIAL returned 6
6

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

(defun factorial-tail-recursion (n)
  (labels ((iterate (n acc)
             (if (= n 0)
                 acc
                 (iterate (1- n) (* acc n)))))
    (iterate n 1)))

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

(defun factorial-tail-recursion (n)
    (factorial-tail-recursion-iterate n 1))
(defun factorial-tail-recursion-iterate (n acc)
  (if (= n 0)
      acc
      (factorial-tail-recursion-iterate (1- n) (* acc n))))

CL-USER> (trace factorial-tail-recursion-iterate)
(FACTORIAL-TAIL-RECURSION-ITERATE)
CL-USER> (trace factorial-tail-recursion)
(FACTORIAL-TAIL-RECURSION)
CL-USER> (factorial-tail-recursion 3)
  0: (FACTORIAL-TAIL-RECURSION 3)
    1: (FACTORIAL-TAIL-RECURSION-ITERATE 3 1)
      2: (FACTORIAL-TAIL-RECURSION-ITERATE 2 3)
        3: (FACTORIAL-TAIL-RECURSION-ITERATE 1 6)
          4: (FACTORIAL-TAIL-RECURSION-ITERATE 0 6)
          4: FACTORIAL-TAIL-RECURSION-ITERATE returned 6
        3: FACTORIAL-TAIL-RECURSION-ITERATE returned 6
      2: FACTORIAL-TAIL-RECURSION-ITERATE returned 6
    1: FACTORIAL-TAIL-RECURSION-ITERATE returned 6
  0: FACTORIAL-TAIL-RECURSION returned 6
6

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

(defun factorial-iteration (n)
  (let ((result 1))
    (loop for i from 1 to n do (setf result (* i result)))
    result))

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

Tail recursion modulo cons

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

list *f(list *input)
{
     list *head;

     if(input == NULL)
     {
          head = NULL;
     }
     else
     {
          head = malloc(sizeof(list));
          head->value = input->value;
          head->next = f(input->next);
     }

     return head;
}

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

list *f(list *input)
{
     list *head;

     fprime(input, &head);
     return head;
}

void fprime(list *input, list **p)
{
     if(input == NULL)
     {
          *p = NULL;
     }
     else
     {
          *p = malloc(sizeof(list));
          (*p)->value = input->value;
          fprime(input->next, &(*p)->next);
     }
}

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

list *f(list *input)
{
     list *head;
     list **p;

     p = &head;
     while(input != NULL)
     {
          *p = malloc(sizeof(list));
          (*p)->value = input->value;
          input = input->next;
          p = &(*p)->next;
     }
     *p = NULL;
     return head;
}