SICP 习题 (1.20) 解题总结

SICP 习题 1.20 又回去讲正则序和应用序了，题目主要是考察书中提到的求最大公约数的过程gcd，问正则序中(gcd 206 40)调用了几次remainder，而应用序中(gcd 206 40)又调用了几次remainder。

gcd过程的定义如下：

(define (gcd a b)
	(if (= b 0)
		a
		(gcd b (remainder a b))))

对于（gcd 206 40)来讲，如果是正则序，展开应该是这样的：

(if (= 40 0)
	206
	(gcd 40 (remainder 206 40)))

现在的关键在于对(gcd 40 (remainder 206 40))的展开。

从过程调用我们知道：

a = 40 
b = (remainder 206 40)

再看过程gcd的定义：

(define (gcd a b)
	(if (= b 0)
		a
		(gcd b (remainder a b))))

每次gcd的调用如果展开的话会包含三次使用b的过程，将(remainder 206 40)代入b中就得到第二次展开的gcd过程。

结果是：

（if (= (remainder 206 40) 0)
	40
	(gcd (remainder 206 40) 
			(remainder a (remainder 206 40))))

通过这样的方法不断展开就可以得到正则序下(gcd 206 40)到底调用了几次remainder过程。

而应用序就很简单了，因为(gcd 206 40)展开成：

	（if (= 40 0)
		206
		(gcd 40 (remainder 206 40)))

对(remainder 206 40)先求值再代入，变成：

	（if (= 40 0)
		206
		(gcd 40 6))

然后继续对(gcd 40 6)进行展开，每次展开只调用了一次remainder。

这个题目再次说明应用序在一般情况下其效率都优于正则序。