空间

探讨递归过程如何消耗空间，栈溢出的成因，以及尾递归如何避免空间无限增长。

递归过程

为了初步探索过程如何使用空间，先看下面这个过程：

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

如果我们手工求值 (factorial 5)，把每一步都写出来，会得到：

start with  (factorial 5)
replaced by (* 5 (factorial 4))
replaced by (* 5 (* 4 (factorial 3)))
replaced by (* 5 (* 4 (* 3 (factorial 2))))
replaced by (* 5 (* 4 (* 3 (* 2 (factorial 1)))))
replaced by (* 5 (* 4 (* 3 (* 2 (* 1 (factorial 0))))))
replaced by (* 5 (* 4 (* 3 (* 2 (* 1 1)))))
replaced by (* 5 (* 4 (* 3 (* 2 1))))
replaced by (* 5 (* 4 (* 3 2)))
replaced by (* 5 (* 4 6))
replaced by (* 5 24)
replaced by 120

每一行都描述了计算的一个新步骤——即为了继续求值，我们在那一刻需要记住的内容。这里有一个关键观察：如果我们给 factorial 选一个足够大的输入，比如 10000，那么在某一步，我们就不可能把整行装进脑子里了。

计算机求值过程调用的方式也是如此。每次函数调用都存储在计算机的工作内存（working memory）中——一个存放中间未完成计算结果的地方。这个空间是有限的，可能被耗尽。要记住的重点是：这个问题只在非常大的输入下才会发生。这种「工作内存」称为「调用栈」（call stack）。当一个程序把这个空间用尽时，就称为「栈溢出」（stack overflow）。

迭代过程

有没有办法改造 factorial，使它在处理大输入时不会让计算机耗尽空间？看看下面这个版本：

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

检验一下你的理解。为什么我们必须写 (> counter max-count)？如果我们调用 (fact-iter 1 1 3) 会发生什么？现在，如果用上面的代码来描绘 (factorial 5)，我们会得到：

start with  (factorial 5)
replaced by (fact-iter 1 1 5)
replaced by (fact-iter 1 2 5)
replaced by (fact-iter 2 3 5)
replaced by (fact-iter 6 4 5)
replaced by (fact-iter 24 5 5)
replaced by (fact-iter 120 6 5)
replaced by 120

在这种情况下，随着求值的推进，我们需要在脑中保留的未完成计算并没有一步步增长。相反，我们通过实参把计算的未完成答案一路传递下去，从而节省了空间。换句话说，计算的完整状态都保存在递归调用的实参中——调用 (fact-iter 2 3 5) 会产生与 (fact-iter 1 1 5) 相同的结果，而调用 (factorial 3) 则会产生与 (factorial 5) 不同的结果。

注意，这个迭代过程仍然使用了递归（recursion），但这与说它是一个「递归过程」不是一回事。

比较迭代过程与递归过程

把这些函数并排来看，我们可以找出这两个过程之间的联系。

递归过程迭代过程
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))(define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count)))

关于两者差异的重要观察：

  • 递归版本中作为基本情况返回的值，在迭代版本中充当 product 的起始值（1）。注意，调用迭代版的 (factorial 1) 会触发 fact-iter 中的基本情况，返回 1。
  • 在递归版本中，* 过程是在递归调用之外调用的；而在迭代版本中，所有实参都在递归调用之前（或之中）完成转换。也就是说，先执行 (* counter product)，然后才进行递归调用。这正是迭代版本更节省空间的关键。
  • 由此可得，这意味着递归调用是过程调用中最后被求值的表达式（而不是某次乘法）。
  • 由于迭代版本需要跟踪更多实参，它需要一个辅助过程，让递归真正在其中发生。迭代过程往往都是这样。

尾递归与编写尾递归过程

用正式的话说，迭代版 factorial 更节省空间，是因为 Racket 解释器实现了尾调用消除（Tail Call Elimination）。在其他编程语言和未做尾调用优化的解释器中，递归版和迭代版运行时会占用同样多的空间。那么，我们为什么还要关心这个问题呢？

  • 介绍这些主题能让我们更深入地理解递归、求值和编程语言，为学习其他主题打下坚实基础。
  • 这是一个练习批判性思考资源使用与权衡的机会，这在软件工程和计算机科学中总体而言都很重要。

要写出尾递归（tail-recursive）的过程，这里有几点建议。

  • 弄清楚你是否需要额外的实参来跟踪计算的状态，以及是否需要一个辅助过程。几乎总是需要某个实参来跟踪「到目前为止的答案」。在 factorial 中，这个实参就是 product。
  • 事实上，一般规律是：过程的递归版本会让实参逐渐变小，而迭代版本则是逐步构建出结果。因此，编写迭代过程时，不妨想想「构建」答案所需的初始值。在 factorial 中，就是 1、1 和 n，即 (fact-iter 1 1 n) 中的三个值。
  • 确保递归调用发生在「最后一刻」。实践中，这意味着实参要先经过处理（相加、相减、相乘、butfirst 等），再发起递归调用。

练习

以下问题用于加深理解，不计成绩。你可以找课程组成员核对答案。

  • 迭代版 factorial 在 fact-iter 中跟踪三样东西。是哪三样？我们能不能再次改写 factorial，让它只跟踪两样东西？
  • 如果使用迭代版本，我们调用 factorial 时还会耗尽空间吗？

延伸阅读

SICP 1.2.1 - 线性递归与迭代（Linear Recursion and Iteration）