11.3.7 无延迟递归

我们再次分析 triangle-recursively 函数的执行过程,会发现中间计算过程会被延迟,直到所有调用完成后才一并执行。

函数定义如下:

(defun triangle-recursively (number)
  "Return the sum of the numbers 1 through NUMBER inclusive.
Uses recursion."
  (if (= number 1)                    ; do-again-test
      1                               ; then-part
    (+ number                         ; else-part
       (triangle-recursively          ; recursive call
        (1- number)))))               ; next-step-expression

当我们以参数 7 调用该函数时会发生什么?

triangle-recursively 的第一个实例会将数字 7 与第二个实例的返回值相加,第二个实例接收的参数为 6。也就是说,第一次计算为:

(+ 7 (triangle-recursively 6))

第一个 triangle-recursively 实例 — 你可以把它想象成一个小机器人 — 无法完成自身任务。它必须将 (triangle-recursively 6) 的计算交给程序的第二个实例,也就是第二个机器人。这个个体与第一个完全不同,用行话说就是“不同实例”。换句话说,它是另一个机器人。型号与第一个相同,都以递归方式计算三角数,但序列号不同。

那么 (triangle-recursively 6) 返回什么?它会将数字 6 与参数为 5 的 triangle-recursively 求值结果相加。用机器人的比喻来说,它会请求另一个机器人协助。

此时总和变为:

(+ 7 6 (triangle-recursively 5))

接下来会发生什么?

(+ 7 6 5 (triangle-recursively 4))

除最后一次外,每次调用 triangle-recursively 都会创建一个新的程序实例 — 另一个机器人 — 并让其执行计算。

最终,完整的加法表达式会被构建并执行:

(+ 7 6 5 4 3 2 1)

该函数的设计会将第一步的计算延迟到第二步完成,第二步又延迟到第三步,依此类推。每次延迟都意味着计算机需要记录等待的内容。在本例这样步骤较少的情况下不会出现问题,但步骤较多时就可能产生问题。