11.3.7 无推迟的递归

让我们再次考虑一下triangle-recursively函数的运行情况。我们会发现中间计算被推迟,直到所有计算都可以完成。

以下是函数定义:

(defun triangle-recursively (number)
  "返回从1加到NUMBER(包括)的数字的和。
使用递归。"
  (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与第二个 triangle-recursively实例的返回值相加,该实例已被传递了一个 参数为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)

这个函数的设计推迟了第一步的计算,直到第二步可以完成,然后推迟到第三步可以完成,依此类推。每个推迟都意味着计算机必须记住正在等待什么。在这个例子中,当步骤很少时,这不是问题。但当步骤更多时,这可能会成为问题。