論壇

尽管在形式上, fact和gcd都是递归的, 但是当fact的输入n大于0时, 在得出(fact (- n 1))的结果之后, Scheme还必须"记住"将该值乘上n, fact的输入越大, 中间积累的记忆也就越多, 反观gcd, 如果b不是0, (gcd b (remainder a b))的结果直接就是(gcd a b)的结果, 记忆不会随着输入规模的增大而增长. 我们称像fact这样的过程呈现了递归计算行为, 而gcd这样的过程呈现了迭代计算行为.

注记: 虽然从原则上gcd描述了一种迭代式计算, 但语言的实现仍有可能指导机器产生递归计算行为.

练习. 观察以下过程.

参数k可以理解为fact求值过程中的记忆, 而(fact-cps n (lambda (v) v))的值就等于(fact n).

请证明对于以下过程fact-iter, 我们有(fact-iter n 1)的值等于(fact n).

并且, 试说明fact-iter和fact-cps之间的联系.

提示: cps是延续传递风格 (continuation-passing style) 的缩写, 延续是对于剩余的计算 (即我们之前所说的"记忆") 的抽象, fact-cps的参数k就代表延续.