SICP
Do you think Computer Science equals building websites and mobile apps?
Are you feeling that you are doing repetitive and not so intelligent work?
Are you feeling a bit sick about reading manuals and copy-pasting code and keep poking around until it works all day long?
Do you want to understand the soul of Computer Science?
If yes, read SICP!!!
This is the first post of this SICP Goodness series, in which I discuss some of my own findings from reading the book SICP.
Since I have to take a long bus trip to work everyday, I decided to use the time to read the SICP (Structure and Interpretation of Computer Programs). And blog along the way to mark the progress.
I have read Chapter 1 and watched the video lectures. But I still feel I get planty new things from going through it again. The best part of this book I think is that it spends minimal time and effort in teaching the programming language, the main focus is the thinking and ideas about programming.
今天通过一个例子，来谈一谈第归的时间和空间效应。
例子很简单，计算 a 的 n 次方。
我们来对比一下两种第归算法的时间和空间的消耗。
第一个方法很直接。思想就是要计算 a 的 n 次方， 只要计算 a 的 (n - 1) 次方， 然后结果在乘以 a 。如下：
(define (expt a n) (if (= n 0) 1 (* a (expt a (- n 1))))) 为了更直观的理解这个算法，我们来计算一个例子， 2 的 3 次方。
(expt 2 3) (* 2 (expt 2 2)) (* 2 (* 2 (expt 2 1))) (* 2 (* 2 (* 2 (expt 2 0)))) (* 2 (* 2 (* 2 1))) (* 2 (* 2 2)) (* 2 4) 8 我们能能明显看到这个算法的“形状”是一个三角形。每一行代表一次计算，也可以理解成时间的消耗。而每一列则代表计算机需要记住的内容，比如说一共要乘以几个2，也可以理解成空间的消耗。我们可以看到，随着 n 的增大， 这个算法的时间和空间消耗也随之增大。而且增大的速度都是线性的。时间的消耗随着 n 的增大而增大很好理解， n 大了， 计算花的时间也相应长了。但是空间消耗可不可以不增大呢？下面我们就来看另一种算法。
今天读到SICP里的一个介绍recursion的例子，用牛顿猜想来计算平方根。
首先，介绍了计算机程序和数学方程的区别。数学方程大多用的是描述法（declarative）。比如说这个平方根，数学上只需要说：
如果x的平方等于y，而且x大于0，那么x就是y的平方根。
这是一种很高层次的描述，通过描述，来限制答案的域。如果能直接用到计算机里，问题就简单了。大概写出来的程序就是这个样子：
func sqrt(x): @ * @ = x; @ > 0; return @; 让计算机去处理计算细节。这当然是一种理想的情况，如果都能这样写程序，那就完事大吉了。这就叫描述性编程(Declarative Programming)。
当然现在还做不到这么绝对，所以我们只能自己写如何进行细节的计算来得到我们的结果。这就叫做命令式变成(Imperative Programming)。
总体来说，描述性编程比命令式编程要容易理解的多，因为不用自己下达命令给计算机，只需要对问题进行描述，计算机自己会找到答案。典型的例子就是xml配置文件，人们把对系统的需求和配置写在一个单独的xml文件里面，然后让计算机自己去执行相应的命令。
好了，现在进入正题。牛顿猜想的原理如下：
要计算x的平方根，先猜想一个答案y，然后用
(y + x / y) / 2
来得到新的优化过猜想。反复进行，知道得到满意的猜想。
首先，我们先来定义一些辅助方程。
(define (abs x) (if (< x 0) (- x) x)) (define (square x) (* x x)) (define (average x y) (/ (+ x y) 2)) 接下来我们来写主程序。
(define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) 这个程序用第归的方法实现了牛顿猜想。
