1.线性的递归和迭代

先从阶乘的问题入手，计算n的阶乘(n!)，也就是：

n!=n*[(n-1)*(n-2)*(n-3)*...3*2*1] = n*(n-1)!

通过n=n*(n-1)!和1!=1，可以将其定义为一个过程：

(define (factorial n)
    (if (= n 1)
        1
        (* n (factorial (-n 1)))))

除了上述过程，还可以另一种方法，用一个计数的counter，累计乘积的sum，按照下面规则变化：

sum       <---- counter * sum    (累计)
counter   <---- counter + 1    (计数)

即n!为计数器counter超过n时乘积sum的值，可以将这个描述重构为：

(define (factorial n)
    (fact-iter 1 1 n))
(define (fact-iter sum counter n)
    (if (> counter n)
        sum
        (fact-iter (*counter sum)
                   (+ counter 1)
                   n)))

如果把计算过程列出，前面第一种计算过程揭示出一种先逐步展开而后收缩的形状，这种类型的计算过程由一个推迟执行的运算链条刻画，称为一个递归计算过程

在计算n!时，推迟执行的乘法链条的长度也就是为保存其轨迹需要保存的信息量，这个长度随着n的增长而线性增长，就像计算中的步骤数目一样，这样的计算过程称为一个线性递归过程

第二种过程里没有增长或收缩，在计算过程中的所有东西就是三个变量，这种过程称为一个迭代计算过程，其状态可以用固定数目的状态变量描述；有固定规则描述这些变量的更新方式；以及结束检测

所需的计算步骤随着n线性增长，这种过程称为线性迭代过程

两种的对比：

• 在迭代的情况里，那几个程序变量都提供了有关计算状态的一个完整描述
• 递归计算过程中，由解释器维持因推迟的运算所形成的链条

混淆点

递归过程：语法形式上的事实，说明这个过程的定义中引用了该过程本身

递归计算过程：计算过程的模式，是指计算过程的进展方式

2.树形递归

以斐波那契数列为切入点，这一序列中的每个数都是前面两个数之和，一般如下规则：

Fib(n) = 0     # if n=0
       = 1     # if n=1
       = Fib(n-1) + Fib(n-2)   # else

将规则定义为过程：

(define (fib n)
    (cond ((= n 0) 0)
          ((= n 1) 1
          (else (+ (fib (-n 1))
                       (fib (- n 2))))))

以fib(5)为例，展开后如下：

反映出对过程的每个调用中两次递归调用自身的事实，这种计算模式称为树形递归

上面定义的过程教育意义居多，其实是不会这么用的，因为它有太多的冗余计算；该过程所用的计算步骤将随着输入增长而指数性地增长，其空间需求只是随着输入增长而线性增长

一般说，树形递归计算过程里所需的步骤数将正比与树中的节点数，其空间需求正比于数的最大深度

3.用迭代计算过程实现斐波那契数列

基本想法：用一对整数a和b；初始化为Fib(1)=1和Fib(0)=0；而后反复同时使用以下变换规则：

a <-- a + b
b <-- a

将n代入可证明出，在第n次应用这些变换后，a和b分别为：Fib(n+1)和Fib(n)，由此可定义过程：

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