例1：计算x^n（X的n次方）
可以采用如下算式来计算：
x^0 = 1
x^n = x*x^(n-1) = x*x*x^(n-2) = ……
那么，很容易得到该计算过程的递归表示：
- (define (exp x n)
- (if (= n 0)
- 1
- (* x (exp x (- n 1)))))
很容易看出来，这个计算的时间和空间复杂度均为O(n)。这便是一个线性递归。为了减少其空间复杂度，可以使用线性迭代来代替（使用递归实现）：
- (define (exp-iter x 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 (fast-exp-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 1))
例2：a*n可以写成a+a*(n-1)的形式。那么采用加法和递归来计算则是：
- (define (mul x n)
- (if (= n 0)
- 0
- (+ x (mul x (- n 1)))))
同样，可以采用迭代的方式来计算：
- (define (mul-iter x n)
- (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))