[原]重新开始学习Scheme（2）：线性递归以及循环不变式

例1：计算x^n（X的n次方）

可以采用如下算式来计算：

x^0 = 1

x^n = x*x^(n-1) = x*x*x^(n-2) = ……

那么，很容易得到该计算过程的递归表示：

(if (= n 0)
    1
    (* x (exp x (- n 1)))))

很容易看出来，这个计算的时间和空间复杂度均为O(n)。这便是一个线性递归。为了减少其空间复杂度，可以使用线性迭代来代替（使用递归实现）：

  (define (iter x n r)
    (if (= n 0)
        r
        (iter x (- n 1) (* r x))))
  (iter x n 1))

计算过程依然有改进空间，那便是可以降低时间复杂度。根据

x^n = x^(n/2)*x^(n/2)

可知，计算x^n的时间复杂度可以降低为O(logn)。此时，需要一个循环不变式来保证计算结果的正确性。设r初始值为1，则在计算过程中，从一个状态迁移到另一个状态（n为奇数迁移到n为偶数）时，r*x^n始终保持不变。而此时计算方法为：

n为奇数，则x^n = x*x^(n-1)

n为偶数，则x^n = x^(n/2)*x^(n/2) = (x^2)^(n/2)

因此，计算过程如下：

  (define (iter x n r)
    (cond ((= n 0) r)
          ((even? n) (iter (* x x) (/ n 2) r))
          (else (iter x (- n 1) (* r x)))))
  (iter x n 1))

例2：a*n可以写成a+a*(n-1)的形式。那么采用加法和递归来计算则是：

  (if (= n 0)
      0
      (+ x (mul x (- n 1)))))

同样，可以采用迭代的方式来计算：

  (define (iter x n r)
    (if (= n 0)
        0
        (iter x (- n 1) (+ r x))))
  (iter x n 0))

与例1相似，也可以将迭代计算的时间复杂度降为O(logn)：

(define (fast-mul-iter x n)
  (define (iter x n r)
    (cond ((= n 0) r)
          ((even? n) (iter (+ x x) (/ n 2) r))
          (else (iter x (- n 1) (+ r x)))))
  (iter x n 0))

这个计算过程的循环不变式是什么呢？