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 (face-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)为例，展开后如下：
fib.jpg
反映出对过程的每个调用中两次递归调用自身的事实，这种计算模式称为树形递归
上面定义的过程教育意义居多，其实是不会这么用的，因为它有太多的冗余计算；该过程所用的计算步骤将随着输入增长而指数性地增长，其空间需求只是随着输入增长而线性增长
一般说，树形递归计算过程里所需的步骤数将正比与树中的节点数，其空间需求正比于数的最大深度
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 (= count 0)
b
(fib-iter(+ a b) a (- count 1))))
网友评论