考虑 Fibonacci 数列：f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2) (n=2, 3, 4, ...)

可以很轻松地写出其递归形式表达（这里使用 Racket）：

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

很显然，这个函数是无法被尾递归优化的。但是我们也可以很简单地将它转化为线性迭代过程：

(define (fib-iter a b n)
  (if (= n 0)
      a
      (fib-iter b (+ a b) (- n 1))))
(define (fib n)
  (fib-iter 0 1 n))

这样做的原理是什么呢？实际上，我们只不过是把每次运算的结果丢弃掉，然后换上下一次需要的数据而已。比如说，我们要计算 f(n+1)，那么就需要知道 f(n-1) 和 f(n)。循环的终止条件是 n=0，然后返回 a。如何验证这样做是正确的？可以列出如下表：

i=n     a=f(0)   b=f(1)
i=n-1   a=f(1)   b=f(2)
i=n-2   a=f(2)   b=f(3)
...
i=1     a=f(n-1) b=f(n)
i=0     a=f(n)   b=f(n+1)

我们得到了我们想要的结果 f(n)！循环终止条件不用 n=1 的理由是：如果一开始传入的 n 就是 0，那么循环将永远无法终止。而使用 n=1 所得到的效率优化微乎其微、可以忽略不计。

可以用完全相同的思路解决 SICP 练习 1.11：写出计算 f(n)=n (n<3), f(n)=f(n-1)+2f(n-2)+3f(n-3)(n>=3) 的递归和迭代的代码。

递归非常简单且自然：

(define (foo n)
  (cond ((< n 3) n)
        (else (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3)))))))

使用相同的表格：

i=n    a=f(0)   b=f(1)   c=f(2)
i=n-1  a=f(1)   b=f(2)   c=f(3)
i=n-2  a=f(2)   b=f(3)   c=f(4)
...
i=0    a=f(n)   b=f(n+1) c=f(n+2)

可以帮助我们写出正确的迭代代码：

(define (foo-iter a b c count)
  (if (= count 0)
      c
      (foo-iter b c (+ (* 3 a) (* 2 b) c) (- count 1))))
(define (foo n)
  (foo-iter 0 1 2 n))

将以上结论推广，可以得到：

若有定义在 N 上的函数 f(n)，对于 n>=N，有 f(n)=A₁f(n-1)+A₂f(n-2)+A₃f(n-3)+...，其中 A₁, A₂, ... 都是常数，那么对于任意 n<N，f(n) 都是需要另行定义的。其递归伪代码必为如下格式：

(define (f n)
  (cond ((n=1) ...)
        ((n=1) ...)
        (...)
        ((n=N) ...)
        (else (+ (* A1 (f (- n 1))
                 (* A2 (f (- n 2))
                 ...))))

其迭代代码一定需要 N 个变量，必为如下格式：

(define (f-iter a b c d e ... count)
  (if (= count 0)
      a
      (f-iter b c d e ... (+ ...) (- count 1))))
(define (f n)
  (f-iter f0 f1 f2 ... fN n))

当 N 比较大时，可能 f(n+1), f(n+2), f(n+3), ..., f(n+N-1) 的计算成本就无法忽略了，这时我们可以在 f 里面想想办法。