9.1. 尾递归函数¶

考虑下面的两个函数。每个函数接收一个非负整数列表，并使用递归返回列表中数字的乘积。

var product1 = function (ns) {
    if (fp.isNull(ns)) {
        return 1;
    } else {
        return fp.mul(fp.hd(ns),
                      product1(fp.tl(ns)));
    }
};

var product2 = function (ns) {
    var helper = function (ns,a) {
          if (fp.isNull(ns))  {
              return a;
          } else {
              return helper(fp.tl(ns),
                            fp.mul(a,fp.hd(ns)));
          }
    };
    return helper(ns,1);
};

哪个版本更好，为什么？要开始回答这个问题，我们需要以下定义。 尾调用 是指作为函数体中最后执行的操作而进行的函数调用。如果一个函数所做的所有递归调用都是尾调用，则该函数是 尾递归 的。我们在 section on the reduce function 中提到了尾递归的概念。现在我们将进一步了解它及其优势。

下面的问题涉及一个递归函数，用于计算两个整数的最大公约数（或 \(gcd\) ）。

9.2. 延续传递风格¶

尾调用消除或优化 （TCO）会自动移除尾调用。随即产生两个问题：我们为什么要这样做？假设我们明白了原因，那么该如何实现呢？

要理解“为什么”，我们首先注意到，如果输入列表包含一个或多个零，则列表中数字的乘积计算应在不进行任何计算的情况下直接返回 0。

对于 product1 函数，在到达基本情况之前不会执行任何计算。但如果输入列表中的第一个零是最后一个数字呢？我们可以省略最后一次递归调用，但仍需通过（可能非常深的）调用栈一路返回 0，并在每次返回时执行一次不必要的乘以 0 的操作。

使用 product2 函数时，TCO 消除了递归调用序列，从而允许我们在发现第一个零时立即返回。然而，由于计算是在每次递归调用之前执行的，因此在检测到第一个零之前可能已经浪费了大量精力。

在这种情况下，我们希望更好地控制程序的执行流程。例如，我们希望在检测到零时立即返回，就像在 TCO'ed product2 中那样；但与此同时，与 product1 一样，在确定输入列表中不存在零之前，我们 不 希望执行任何耗时的计算。

续体 使我们能够显式地表达程序的控制流和执行状态，从而解决这一问题。

续传 是一个回调函数 \(k\) ，表示程序执行的当前状态。更准确地说，续传 \(k\) 是一个单参数函数，该参数是迄今为止已计算出的值，它在程序剩余部分运行完成后返回计算的最终值。

因此，在我们的乘积示例的计算过程中的任何一点，延续 \(k\) 将迄今为止已计算的部分乘积 \(x\) 作为输入，并返回最终乘积。当然，最终乘积仍然是递归计算的。所以 \(k\) 只执行一次乘法运算，然后调用另一个延续来处理列表的其余部分。

例如，若输入列表为 [2,3,4,5,6]，则在处理完 3 之后，续体是一个函数，它接受 \(x=6=2\times 3\) 作为输入，计算下一个乘积（即 \(x \times 4\) ），最后将该新值作为输入传递给下一次递归调用的续体。[注意：实际上，在这种情况下，乘积的计算顺序是反向的，从列表末尾向头部进行，但这一点在此处属于细节问题]。

要了解延续的概念如何实际导出乘积函数的新尾递归版本，请阅读以下幻灯片中关于 product3 函数的描述。

Settings

Saving...
Server Error
Resubmit

下一张幻灯片将回顾我们目前为止见过的三个版本的乘积函数。

Settings

Saving...
Server Error
Resubmit

除了提供一种保证 TCO 可执行的技术外，CPS 相较于直接递归和累加技术还具有其他一些优势。首先，假设我们希望确保当输入列表包含零时不会执行任何不必要的计算。我们可以定义一个名为 product4 的新改进版函数，如下所示。

var product4 = function (ns) {
    var cps_zero = function (ns,k) {
        if (fp.isNull(ns)) {
            return k(1);
        } else if (fp.isEq(fp.hd(ns),0)) {
            return 0;  // *** the continuation is never invoked! ***
        } else {
            return cps_zero(fp.tl(ns),
                            function (x) {
                                return k(fp.mul(x,fp.hd(ns)));
                            });
        }
    };
    return cps_zero(ns, function (x) { return x; });
};

请注意，尽管我们可以在 product1 函数中添加一个类似的分支来返回 0，但在递归回退过程中，这个返回的 0 会被不必要地用于多次计算。我们也可以在 product2 中添加一个类似的“返回 0"分支，但等到遇到零时，累加器参数可能已经执行了许多不必要的乘法运算。

为了说明使用延续传递风格的函数的另一个巧妙之处，请回想一下输入列表中不允许出现负数。因此，我们可以将列表中错误地出现负数视为一种异常，对于这种异常，我们希望立即抛出错误消息并放弃乘积的计算，而不执行任何乘法运算。下面函数中的 product5 版本展示了如何使用延续传递风格以这种方式处理异常。

var product5 = function (ns) {
    var cps_exception = function (ns,k) {
        if (fp.isNull(ns)) {
            return k(1);
        } else if (fp.isEq(fp.hd(ns),0)) {
            return 0;
        } else if (fp.isLT(fp.hd(ns),0)) {
            return "Negative numbers are not allowed.";
        } else {
            return cps_exception(fp.tl(ns),
                                 function (x) {
                                     return k(fp.mul(x,fp.hd(ns)));
                                 });
        }
    };
    return cps_exception(ns, function (x) { return x; });
};

在 product1 中添加这样一个返回字符串的异常处理情形是不可能的，因为该字符串必须参与从递归展开时发生的所有乘法运算。虽然我们可以在 product2 中添加这样的情形，但这会违背异常处理的主要目标之一，即保护关键变量的值免受在遇到异常之前可能发生的“损害”。尽管 product2 足够简单，以至于在异常发生前不会出现任何有害的副作用，但在更复杂的情况下，累加器技术无法避免这个问题，因为它会在深入递归调用的过程中执行计算。相比之下，product5 在遇到异常时完全没有执行任何计算。相反，它所做的只是部分定义了续体函数，而我们在遇到异常时可以无害地决定不调用该函数。

9.3. 延续传递风格练习题（第 1 部分）¶

以下问题是连续三个问题中的第一个，要求你完成一个使用延续传递风格编程的递归函数的实现。本问题使用了本组第一个问题中引入的 \(gcd\) 函数，但你无需记住其具体实现方式。

9.4. 延续传递风格练习题（第 2 部分）¶

下列问题是一组三个问题中的第二个，要求你完成一个使用续体传递风格编程的递归函数的实现。本问题使用了本组第一个问题中引入的 \(gcd\) 函数，但你无需记住它是如何实现的。

9.5. 延续传递风格练习题（第 3 部分）¶

下列问题是一系列三个问题中的最后一个，要求你完成一个使用续体传递风格编程的递归函数的实现。本问题使用了本组第一个问题中引入的 \(gcd\) 函数，但你无需记住它是如何实现的。

9.6. 更多 CPS 练习¶

这个随机复习题将让你有更多练习以续传风格编写递归函数的机会。要获得分数，你必须连续三次正确解答它。