通过模型对程式的解析，可以得到计算过程，其中一些过程因为结构较通用，所以被整理为典型过程供大家学习。需要注意的是，在计算过程的学习中要分清程式与过程的区别，过程是通过模型对程式的解析产生的计算步骤，所以一个递归的程式其过程可能是迭代的。
线性递归
我们使用替换模型分析时可能会发现，有些程式的过程会先展开再收敛，通常这种过程就是递归过程，又因为该过程的时间增长趋势为 O(n)。所以称为线性递归过程，其空间增长趋势也为 O(n)。比如，下列计算阶乘的程式为线性递归过程：
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
解析后的计算过程如下图：
recursive process
线性迭代
线性迭代也是通过替换模型解析程式时生成，此类过程即不会展开也不会收敛，但在每一步都会保存当前步骤的状态数据，依靠状态数据的迭代产生下一步计算。也因为该过程的时间增长趋势 O(n)，所以又称为线性迭代过程。
虽然线性迭代过程的时间增长趋势与线性递归过程一样，但线性迭代过程空间增长趋势为 `O(1)
，并且可以通过当前步骤存储的状态数据随时重启程序。
例如，下列计算阶乘的程式为线性迭代过程：
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* product counter)
(+ counter 1)
max-count)))
解析后的计算过程如下图：
iterative process
树形递归
树形递归也是通过替换模型分析产生，树形递归在一个表达式中会进行多次递归调用，形成类似树形的递归计算过程，所以称为树形递归过程，此过程的时间消耗是指数级的，与树形的节点呈正相关性，消耗的空间与树的最大深度呈正相关性。
树形递归存在大量的冗余计算，因此它的计算效率并不高，但它描述及解决某些问题更加直观（例如继承类型的数据），所以它也是一种设计程序的重要工具。
下列计算斐波那契数列的程度为树形递归过程：
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
解析后的计算过程如下图：
tree recursion
网友评论