1.2 Procedures and the Processes

通过模型对程式的解析，可以得到计算过程，其中一些过程因为结构较通用，所以被整理为典型过程供大家学习。需要注意的是，在计算过程的学习中要分清程式与过程的区别，过程是通过模型对程式的解析产生的计算步骤，所以一个递归的程式其过程可能是迭代的。

线性递归

我们使用替换模型分析时可能会发现，有些程式的过程会先展开再收敛，通常这种过程就是递归过程，又因为该过程的时间增长趋势为 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