线性递归:书中P21的代换模型看到伸展和收缩两个阶段,且伸展阶段所需的额外存储量和计算所需的步数都正比于参数
线性迭代:P22只使用常量存储大小,且计算所需的步骤正比于参数
树形递归:单纯按照数学上的解法,对最终结果进行逆推,其前面的每个部分需要更前面的部分进行分解。为了减少计算所需的空间,采用自底至上的迭代方法。从树变成一条直线。
此解法一般需要一个变量存储计算次数;另外几个变量存储中间变量,每经过一次迭代交换它们的值。
参考答案,根据题中所给的公式,f(n)由n-1至n-3的函数结果决定,所以我们用变量 i 作为渐进下标(i=0开始), n 作为最大下标。 a 、 b 和 c 分别代表函数调用f(i+2) ,f(i+1) 和 f(i)的值。
(define (f n)(f-iter 2 1 0 0 n))(define (f-iter a b c i n)(if (= i n)c(f-iter (+ a (* 2 b) (* 3 c)) ; new aa ; new bb ; new c(+ i 1)n)))