No deferment solution (翻译: Emacs Lisp 编程)

Previous: 无延迟递归, Up: Recursion [Contents][Index]

11.3.8 无延迟解决方案 ¶

解决操作延迟问题的方案是采用不会延迟操作的编写方式¹⁶。这通常需要采用不同的模式，往往需要编写两个函数定义：一个初始化函数和一个辅助函数。

初始化函数负责启动任务，辅助函数负责实际执行工作。

下面是用于数字求和的两个函数定义。它们非常简洁，我初次理解时也颇费功夫。

(defun triangle-initialization (number)
  "Return the sum of the numbers 1 through NUMBER inclusive.
This is the initialization component of a two function
duo that uses recursion."
  (triangle-recursive-helper 0 0 number))

(defun triangle-recursive-helper (sum counter number)
  "Return SUM, using COUNTER, through NUMBER inclusive.
This is the helper component of a two function duo
that uses recursion."
  (if (> counter number)
      sum
    (triangle-recursive-helper (+ sum counter)  ; sum
                               (1+ counter)     ; counter
                               number)))        ; number

对两个函数定义求值使其生效，然后以 2 行调用 triangle-initialization：

(triangle-initialization 2)
    ⇒ 3

初始化函数会以三个参数调用辅助函数的第一个实例：0、0 和三角数的行数。

传递给辅助函数的前两个参数为初始化值。这些值会在 triangle-recursive-helper 调用新实例时更新。¹⁷

我们来看只有一行的三角数情况。（该三角数只包含一个石子！）

triangle-initialization 会以参数 0 0 1 调用其辅助函数。该函数会运行条件测试 (> counter number)：

(> 0 1)

结果为假，因此会执行 if 语句的 else 分支：

    (triangle-recursive-helper
     (+ sum counter)  ; sum plus counter ⇒ sum
     (1+ counter)     ; increment counter ⇒ counter
     number)          ; number stays the same

首先计算：

(triangle-recursive-helper (+ 0 0)  ; sum
                           (1+ 0)   ; counter
                           1)       ; number

which is:


(triangle-recursive-helper 0 1 1)

再次判断，(> counter number) 仍为假，因此 Lisp 解释器会再次对 triangle-recursive-helper 求值，以新参数创建一个新实例。

这个新实例为：

    (triangle-recursive-helper
     (+ sum counter)  ; sum plus counter ⇒ sum
     (1+ counter)     ; increment counter ⇒ counter
     number)          ; number stays the same

which is:


(triangle-recursive-helper 1 2 1)

此时，(> counter number) 测试结果为真！因此该实例会返回总和的值，即预期的 1。

现在，我们给 triangle-initialization 传入参数 2，查看两行三角数包含多少个石子。

该函数会调用 (triangle-recursive-helper 0 0 2)。

依次调用的实例为：

                          sum counter number
(triangle-recursive-helper 0    1       2)

(triangle-recursive-helper 1    2       2)

(triangle-recursive-helper 3    3       2)

当最后一个实例被调用时，(> counter number) 测试为真，因此该实例会返回 sum 的值，即 3。

这种模式在编写可能大量占用计算机资源的函数时非常有用。

Footnotes

(16)

尾递归(tail recursive) 这一术语即用于描述这类占用常量空间的过程。

(17)

这种说法略微容易混淆：triangle-recursive-helper 在一个递归过程中使用了迭代式的执行流程。称其过程为迭代，是因为计算机只需记录 sum、counter 和 number 三个值；称其过程为递归，是因为函数会调用自身。而 triangle-recursively 的执行流程与过程本身均被称为递归。“递归(recursive)”一词在不同语境下含义不同。