11.3.8 无推迟解决方案

解决推迟操作的问题的方法是以不推迟操作的方式编写代码13。这需要编写一个不同的模式,通常涉及编写两个函数定义,一个初始化函数和一个辅助函数。

初始化函数设置任务;辅助函数执行工作。

以下是两个求和的函数定义。它们非常简单,我发现它们很难理解。

(defun triangle-initialization (number)
  "返回从1加到NUMBER(包括)的数字的和。
这是使用递归的两个函数对的初始化组件。"
  (triangle-recursive-helper 0 0 number))
(defun triangle-recursive-helper (sum counter number)
  "使用COUNTER返回SUM,通过NUMBER(包括)。
这是使用递归的两个函数对的辅助组件。"
  (if (> counter number)
      sum
    (triangle-recursive-helper (+ sum counter)  ; sum
                               (1+ counter)     ; counter
                               number)))        ; number

通过评估这两个函数定义来安装它们,然后使用2行调用triangle-initialization

(triangle-initialization 2)
    ⇒ 3

初始化函数使用三个参数调用辅助函数的第一个实例:零,零,以及三角形中的行数。

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

让我们看看当我们有一个只有一行的三角形时会发生什么。(这个三角形将有一个小石子!)

triangle-initialization将使用参数0 0 1调用它的辅助函数。该函数将运行条件测试,即(> counter number)

(> 0 1)

并发现结果为假,因此它将调用if子句的else部分:

    (triangle-recursive-helper
     (+ sum counter)  ; sum加countersum
     (1+ counter)     ; 增加countercounter
     number)          ; number保持不变

这将首先计算:

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

(triangle-recursive-helper 0 1 1)

再次,(> counter number)将为假,因此Lisp解释器将评估triangle-recursive-helper,创建一个新实例并传递新参数。

这个新实例将是:

    (triangle-recursive-helper
     (+ sum counter)  ; sum加countersum
     (1+ counter)     ; 增加countercounter
     number)          ; number保持不变

即:

(triangle-recursive-helper 1 2 1)

在这种情况下,(> counter number)测试将为真!因此,该实例将返回sum的值,该值将是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

(13)

术语尾递归用来描述这种使用常量空间的过程。

(14)

术语有点混乱:triangle-recursive-helper在递归的过程中使用迭代的方式,因为计算机只需记录三个值sumcounternumber;而该过程在递归的过程中使用递归的方式,因为函数调用了自身。另一方面,triangle-recursively使用的过程和过程都被称为递归。在这两种情况下,“递归”这个词在两个上下文中有不同的含义。