举例分析迭代及递归的复杂度（scheme代码实现）

分别用递归和迭代的方式实现下述的公式：

$\frac{2\cdot4\cdot4\cdot6\cdot6\cdot8}{3\cdot3\cdot5\cdot5\cdot7\cdot7}$

分子部分的规律为：从第二个开始，每两个数递增一次。因此，可以用如下公式表示：

$x_{n}=[div(n,2)+1]\times2$

其中div(n,2)表示n整除2得到的结果。
用程序计算分子中第n个数的值，如下所示：

(define (numerator-num n)
  (* (+ (quotient n 2)
        1)
     2))

分母部分的规律为：从第一个开始，每两个数递增一次。因此，可以用如下公式表示：

$y_{n}=div(n+1,2)\times2+1$

用程序计算分母中第n个值，如下所示：

(define (denominator-num n)
  (+ (* (quotient (+ n 1) 2)
     2)
     1))

对于类似

$\sum_{n=a_1}^{a_n}f(n)=f(a_1)\times...{\times}f(a_n)$

既可以用递归，也可以用迭代的形式得到。
（1）递归表示

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

代码中product是过程名，term是公式中的函数f，a是起始计算值（也就是公式中的a1），b的终止运算值（也就是公式中的an）。next指的是a(k)变化到a(k+1)的规律，比如对于公式中的分子分母而言，a(k)=k，a(k+1)=k+1，因此这里的next就是进行加一操作。递归的思想是通过反复调用过程product，得到最终的结果：

$\sum_{n=a_1}^{a_n}f(n)=f(a_1)\times...{\times}f(a_n)=f(a_1)\times\sum_{n=a_2}^{a_n}f(n)=f(a_1)f(a_2)\times\sum_{n=a_3}^{a_n}f(n)$

用程序表示过程，可以表示为：

$(product~f~a_{1}~next~a_{n})=f(a_1)\times(product~f~a_{2}~next~a_{n})\\begin{matrix}&&&&&&&&&&&&&\&&&&&&&&&&&&&\end{matrix}=f(a_1)f(a_2)\times(product~f~a_{3}~next~a_{n})\\begin{matrix}&&&&&&&&&&&&&\\end{matrix}=f(a_1)f(a_2)f(a_3)\times(product~f~a_{4}~next~a_{n})$

（2）迭代表示

(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* (term a) result))))
  (iter a 1))

迭代与递归最根本的区别在于：递归会不停地展开，直到完全展开，然后开始代入计算；迭代会不停的对数据进行替代，而不会展开数据。比如该段代码的公式表示为：![][7]
result值会在迭代过程中不断更新，直到最后将result输出。

$\frac{2\cdot4\cdot4\cdot6\cdot6\cdot8}{3\cdot3\cdot5\cdot5\cdot7\cdot7}$

其实有两种实现方式，一种是分别迭代或递归分子和分母，最后将分子和分母相除；另一种是讲对应项的分子和分母看作整体，再进行迭代或递归。

$\frac{2}{3}\cdot\frac{4}{3}\cdot\frac{4}{5}\cdot\frac{6}{5}\cdot\frac{6}{7}\cdot\frac{8}{7}$

因此，可以得到2中不同的递归和迭代方式。
（1）递归方式1：分子分母分别递归，最后再相除。

#lang planet neil/sicp
(#%require (only racket/base current-inexact-milliseconds))


(define (fraction n)
  (define start-time (current-inexact-milliseconds))
  (/ (numerator n)
     (denominator n))
  (newline)
  (define end-time (current-inexact-milliseconds))
  (display (- end-time start-time)))

(define (numerator n)
  (define (fractions-next x) (+ x 1))
  (product numerator-num 1 fractions-next n))

(define (denominator n)
  (define (fractions-next x) (+ x 1))
  (product denominator-num 1 fractions-next n))

(define (numerator-num n)
  (* (+ (quotient n 2)
        1)
     2))

(define (denominator-num n)
  (+ (* (quotient (+ n 1) 2)
     2)
     1))

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

（2）递归方式2：分子分母看作一个整体，再进行递归。

#lang planet neil/sicp
(#%require (only racket/math pi))
(#%require (only racket/base current-inexact-milliseconds))


(define (fraction n)
  (define start-time (current-inexact-milliseconds))
  (define (fractions-next x) (+ x 1))
  (product fraction-num 1 fractions-next n)
  (define end-time (current-inexact-milliseconds))
  (display (- end-time start-time)))


(define (fraction-num n)
  (/ (numerator_num n)
     (denominator_num n)))


(define (numerator_num n)
  (* (+ (quotient n 2)
        1)
     2))

(define (denominator_num n)
  (+ (* (quotient (+ n 1) 2)
     2)
     1))


(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

（3）迭代方式1：分子分母分别迭代，最后再相除。

#lang planet neil/sicp
(#%require (only racket/base current-inexact-milliseconds))

(define (fraction n)
  (define start-time (current-inexact-milliseconds))
  (/ (numerator n) (denominator n))
  (newline)
  (define end-time (current-inexact-milliseconds))
  (display (- end-time start-time)))

(define (numerator n)
  (define start-time (current-inexact-milliseconds))
  (define (fractions-next x) (+ x 1))
  (product numerator_num 1 fractions-next n))

(define (denominator n)
  (define (fractions-next x) (+ x 1))
  (product denominator_num 1 fractions-next n))

(define (numerator_num n)
  (* (+ (quotient n 2)
        1)
     2))

(define (denominator_num n)
  (+ (* (quotient (+ n 1) 2)
     2)
     1))

(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* (term a) result))))
  (iter a 1))

（4）迭代方式2：分子分母看作一个整体，再进行迭代。

#lang planet neil/sicp
(#%require (only racket/base current-inexact-milliseconds))

(define (fraction n)
  (define start-time (current-inexact-milliseconds))
  (define (fractions-next x) (+ x 1))
  (product fraction-1num 1 fractions-next n)
  (newline)
  (define end-time (current-inexact-milliseconds))
  (display (- end-time start-time)))

(define (fraction-1num n)
  (/ (numerator_num n)
     (denominator_num n)))

(define (numerator_num n)
  (* (+ (quotient n 2)
        1)
     2))

(define (denominator_num n)
  (+ (* (quotient (+ n 1) 2)
     2)
     1))

(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* (term a) result))))
  (iter a 1))

分别使用上述迭代和递归方法，计算n=1000，重复计算50次，记录下每次运算时间，如下图所示。

[7]: http://latex.codecogs.com/svg.latex?(iter~~a_{1}~~result)=(iter~~a_{2}~~(f(a_{1}){\times}result))=(iter~~a_{3}~~(f(a_{2}){\times}result))

举例分析迭代及递归的复杂度（scheme代码实现）

推荐阅读更多精彩内容