目前从 1.2 开始做笔记, 之前的可能会, 也可能不会补上.
1.2
1.2.1 线性的递归和迭代
在各种常见语言的大部分实现的设计中, 对于任何递归过程的解释, 所消耗的存储量总与过程调用 数目成正比, 即使它所描述的计算过程从原理上来看是迭代的.
大部分语言中, 书写形式是递归, 但是处理逻辑是迭代的.
练习 1.9
1
2
3
4
5
6
7
8
9
10
11
12
13
| # 题干
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
# 计算 (+ 4 5)
# 计算过程是递归的或者迭代的吗
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| # 定义1
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9
# 结论: 以上递归过程属于线性递归计算过程
# 定义 2
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
0
# 结论: 以上递归过程属于线性迭代计算过程
|
引用 SICP 习题集 中的话:
- 从计算过程中可以很明显地看到伸展和收缩两个阶段，且伸展阶段所需的额外存储量和计算所需的步数都正比于参数 a ，说明这是一个线性递归计算过程。
- 从计算过程中可以看到，这个版本的 plus 函数只使用常量存储大小，且计算所需的步骤正比于参数 a ，说明这是一个线性迭代计算过程。
联系 1.10
1
2
3
4
5
6
7
8
9
| # (A 1 10)
(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
# ...
(A 0 (A 0 ... (A 0(A 1 1)))) # 9 个 (A 0 ...)
(A 0 (A 0 ... (A 0 2))) # 9 个 (A 0 ...)
2^10
|
1
2
3
4
5
6
7
8
| # (define (g n)
# (A 1 n))
(g n)
(A 1 n)
(A 0 (A 1 (- n 1)))
...
# 2^n
|
树形递归
一般来说, 树形递归计算过程里所需的步骤数将正比于树中的节点数, 其空间需求正比于数的最大深度.