SICP 1.2节读书笔记

发表于 更新于 分类于 本文字数： 1k 阅读时长 ≈ 1 分钟

Procedure and Process

1.2.1 线性递归处理（Linear Recursion Process）与迭代处理（Iteration Process）

线性递归处理

递归处理(Recursive Process)是指由一些推迟的操作（Defered operation）构成的处理链。 这些操作的结果无法依赖现有的信息得到，只能推迟到信息充足时才能够从递归的内部往外计算。如， 计算阶乘时采用以下迭代式： \begin{equation} n!=n(n-1)! \end{equation}

在Scheme中定义函数如下：

1
2
3
4
5
6
(def (factorial x)
     (if (= x 1)
         1
         (* x (factorial (- x 1)))
      )
)

如果要执行(factorial 4)，它的执行情况如下：

1
2
3
4
5
6
7
(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24

在得到结果的过程中，可以看到在头3步的递归调用。在这个过程中，解释器在后台自动记录了整 个计算过程。在通常的编程语言中，这个计算过程的中间变量将会被记录在栈上，这一片内存由系统自 动管理。所需要内存量随调用深度线性增长。所以这个处理过程又被称为线性递归处理。

迭代处理

迭代处理（Iterative Process）是通过操作所有的状态，逐步迭代得到最终结果。使用迭代 处理需要能够找出完成这一函数的所有状态。以计算加法为例： \begin{equation} c=a+b=(a-1)+(b+1)=\dots=(a-a)+(b+a)=0+b+a \end{equation}

在Scheme中定义函数如下：

1
2
3
4
5
6
7
8
(define (dec x) (- x 1))
(define (inc x) (+ x 1))
(define (+ a b)
     (if (= a 0)
         b
         (+ (dec a) (inc b))
     )
)

如果要执行(+ 3 1)，其执行过程如下：

1
2
3
4
(+ 2 2)
(+ 3 1)
(+ 4 0)
4

显然在这种模式下，解释器不必要去保存中间变量，直接将最后的结果作为结果就行。理想中，这种 调用过程是不会产生额外的内存开销的。但是在通常的编程语言，如C中，系统要维护调用栈，即使 是这种写法，仍然会产生额外的内存开销。此时，可以通过将递归改写成由循环免去调用过程的代价。 这种技法叫尾递归。Scheme在解释器层面进行了尾递归优化，所以在上述执行过程中是没有额外内 存开销的。