;;; p8-sum-of-squares.scm

(define (sum-of-squares x y)
    (+ (square x)
       (square y)))

           x < y
          /    \
         /      \
        /        \
    x < z         y < z
     / \           / \
    /   \         /   \
x < y  x < y   y < x  y < x
x < z  z < x   y < z  z < y

(if (> x y)
    ; x 较大
    (if (> y z)
        ; x 和 y 较大
        ; x 和 z 较大)
    ; y 较大
    (if (> x z)
        ; y 和 x 较大
        ; y 和 z 较大))

(cond ((and (> x y) (> y z))
        ; x 和 y 较大)
      ((and (> x y) (> z y))
        ; x 和 z 较大)
      ((and (> y x) (> x z))
        ; y 和 x 较大)
      ((and (> y x) (> z x))
        ; y 和 z 较大))

;;; 3-bigger-and-smaller.scm

(define (bigger x y)
    (if (> x y)
        x
        y))

(define (smaller x y)
    (if (> x y)
        y
        x))

(define bigger (bigger x y))
(define another-bigger (bigger (smaller x y) z))

(define (sqrt-iter old-guess x)
    (let ((new-guess (improve old-guess x)))
        (if (good-enough? old-guess new-guess)
            new-guess
            (sqrt-iter new-guess x))))

练习1.8例题使用此公式：(x/(y^2) + 1) / 2   < 精确值若使用此公式求立方根，给出过程

原例题 (define (new-sqrt guess x)　　　　　　(if （good-enough? guess x)　　　　　　　　　guess　　　　　　　　　(sqrt-iter (improve guess x)　　　　　　　　　　　　　　　　x)))

(define (improve guess x)　　(tri-average (* 2 guess) (/ x guess)))good-enough里改为cube即可

1.8 过程作为黑箱抽象

分解使每一个过程可以被用作定义其他过程的模块例如，基于square定义过程good-enough？，就是将square看做一个“黑箱”square纪委几个过程的抽象，即过程抽象过程用户不必去关心的细节：局部名：　　形式参数的具体名字对过程体完全没有关系，称约束变量内部定义和块结构：　　嵌套称为块结构　将x作为内部定义中的*变量，x有实际参数得到自己的值，称为词法作用域

　

2，过程与他们所产生的计算

过程所产生的计算过程的“形状” 及所消耗各种重要计算资源（时间空间）的速率

1，线性的递归和迭代阶乘 n！(define (factorial n)　　(if (= n 1) 　　　　1　　　　 (* n (factorial (- n 1)))))

递归：在展开阶段里， 这一计算过程构造起一个推迟进行的操作所形成的两条，收缩阶段表现为这些运算的实际执行这种类型的计算过程又一个推迟记性的运算链条刻画，称为一个递归计算过程推迟执行的乘法链条的长度（即位保存其轨迹需要保存的信息量）随n值而线性增长（正比于n）　　　过程是递归的，说明这个过程的定义中（直接或间接）引用了该过程本身

迭代：　　可以用状态变量描述尾递归：在常量空间中执行含有迭代型计算过程的递归过程

练习 1.9inc：将参数增加1dec：将参数减少1(define (+ a b)　　(if (= a 0)　　　　 b　　　　 (inc (+ (dec a) b))))(define (+ a b)　　(if (= a 0)　　　　 b　　　　　　 (+ (dec a) (inc b))))请用代换模型展示这两个过程在求值（+ 4 5）时所产生的计算过程。区分是迭代还是递归》答案：　　第一个调用本身了，是递归过程，计算过程是迭代　　(plus 3 5) 进行求值，表达式的展开过程为：

(plus 3 5)
(inc (plus 2 5))
(inc (inc (plus 1 5)))
(inc (inc (inc (plus 0 5))))
(inc (inc (inc 5)))
(inc (inc 6))
(inc 7)
8

从计算过程中可以很明显地看到伸展和收缩两个阶段，且伸展阶段所需的额外存储量和计算所需的步数都正比于参数 a ，说明这是一个线性递归计算过程。

另一个 + 函数的定义如下(为了和内置的 + 区分开来，我们将函数改名为 plus)：

;;; 9-another-plus.scm

(load "9-inc.scm")
(load "9-dec.scm")

(define (plus a b)
    (if (= a 0)
        b
        (plus (dec a) (inc b))))
对 (plus 3 5) 进行求值，表达式的展开过程为：

(plus 3 5)
(plus 2 6)
(plus 1 7)
(plus 0 8)
8
从计算过程中可以看到，这个版本的 plus 函数只使用常量存储大小，且计算所需的步骤正比于参数 a ，说明这是一个线性迭代计算过程。

练习 1.10Ackermann函数(define (A x y)　　(cond ((= y 0) 0)　　　　　 ((= x 0) (* 2 y))　　　　　 ((= y 1)  2) 　　　　　(else (A (- x 1)　　　　　　　　　　　(A x (- y 1))))))

1 ]=> (load "10-ackermann.scm")

;Loading "10-ackermann.scm"... done
;Value: a

1 ]=> (A 1 10)

;Value: 1024

1 ]=> (A 2 4)

;Value: 65536

1 ]=> (A 3 3)

;Value: 65536

接着，我们通过给定一些连续的 n ，来观察题目给出的几个函数，从而确定它们的数学定义。

首先是 (define (f n) (A 0 n)) ：

可以看出，函数 f 计算的应该是 2* n

然后是 (define (g n) (A 1 n)) ：

可以看出，函数 g 计算的应该是2的n次方

最后是 (define (h n) (A 2 n)) ：

超过 4 之后，再调用函数 h 就会出现超出解释器最大递归深度的现象

1.2.2树形递归 Fibonacci数序列　　每个数都是前面两个数之和第一种方法，递归法，翻译定义　(define (fib n)　　　(cond ((= n 0) 0)　　　　　　 ((= n 1) 1)　　　　　　 (else (+ (fib (- n 1))　　　　　　　　　　　　(fib (- n 2))))))

此函数Fib(n)值的增长相对于n是指数的，Fib(n)就是最接近 (Φ^n) / √5 的整数

Φ = (1 + √5) / 2 =1.6180....    即黄金分割的值

Φ^2 = Φ + 1

即该过程所用的计算步骤将随着输入增长而指数性的增长

　　　　　　　空间需求是随着输入增长而线性增长

这样在计算中的每一点，只需保存书中在此之上的结点的轨迹

一般说，树形递归计算过程里所需的步骤数将正比与树中的结点数，其空间需求正比于数的最大深度。

第二种，迭代方法

int a b ，初始化为Fib(1) = 1 和 Fib(0) = 0

迭代规则：a = a + b

　　　　 b = a

n次变后，a和b 分别等于Fib(n + 1) 和 Fib(n)

即：

　　(define (fib n)

　　　　(fib-iter 1 0 n))

　　(define (fib-iter a b count)

　　　　(if ( = count 0)

　　　　　  b

　　　　　  (fib-iter ( + a b)  a  (- count 1))))

第二种方法相对于n为线性的

实例：换零钱方式的统计

美元换为 半美元、四分之一美元、10美分、5美分 和 1美分

将总数为a的现金换成 n 种硬币的不同方式的数目等于

　　甲。将现金数 a 换成除第一种之外的所有其他硬币的不同方式数目，加上

　　乙。将现金 a-d 换成所有种类的硬币的不同方式数目，其中的 d 是第一种硬币的币值

　　a = 0 , 1种换零钱的方式

　　a < 0 , 0种

　　n = 0 , 0种

(define (count-change amount)

　　(cc amount 5))

(define (cc amount kinds-of-coins)

　　(cond ((= amount 0) 1)

　　　　　 ((or (< amount 0)  (= kinds-of-coins 0)) 0)

　　　　　 (else (+ (cc  amount                              ; n次之后   甲数目

　　　　　　　　　    　  (-  kinds-of-coins 1))

　　　　  　　　　　(cc  (-  amount                          ; n次之后 乙数目

　　　　　　　　　　　　　  (first-denomination kinds-of-coins))

　　　　　　　　　　　 　kinds-of-coins)))))

(define (first-denomination kinds-of-coins)

　　(cond ((= kinds-of-coins 1) 1)

　　　　　((= kinds-of-coins 2) 5)

　　　　   ((= kinds-of-coins 3) 10)

　　　　　((= kinds-of-coins 4) 25)

　　　　　((= kinds-of-coins 5) 50)))

练习1.11

函数 f 由如下的规则定义；如果 n <  3, 那么f (n) = n; 如果n>=3，那么f(n) =f(n-1)+2f(n-2) + 3f(n-3)

写出一个采用递归计算过程计算 f 的过程 和 一个采用迭代计算过程计算 f 的过程

递归：recursion

　　(define (f n)

　　　　(cond (<   n 3) n)

　　　　　　   (>= n 3)

　　　　　　　　 (+ f(- n 1)

　　　　　　　　　　(* 2 f(- n 2)

　　　　　　　　　　(* 3 f(- n 3)))))) 　　　　　　　　

迭代：iteration

　　(define (ff n)

　　　　(+ 2 (* 2 (f 1)) (* 3 (f 0)))..

解题集答案：

递归：

(define (f n)
    (if (< n 3)
        n
        (+ (f (- n 1))
           (* 2 (f (- n 2)))
           (* 3 (f (- n 3))))))

迭代：

要写出函数f 的迭代版本，关键是在于看清初始条件和之后的计算进展之间的关系，

根据函数 f 的初始条件 “如果 n < 3，那么f(n) = n ",有等式

f(0) = 0

f(1) = 1

f(2) = 2

当 n >= ，有f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)

迭代版函数定义如下：它使用 i 作为渐进下标， n作为最大下标， a、b和c三个变量分别代表函数调用 f (i + 2)  、f(i + 1)、f(i)，从f(0)  开始计算

(define (f n)

　　(f-iter 2 1 0 0 n))

(define (f-iter a b c i n)

　　(if (= i n)

　　　  c

　　　 (f-iter (+ a (* 2 b)  (* 3 c))             ; new a

　　　　　　　a　　　　　　　　　　　　　　; new b

　　　　　　　b　　　　　　　　　　　　　　; new c

　　　　　　   (+ i  1)

　　　　　　 n)))

效率对比：

　　递归版本的函数 f 有很多多余的计算，例如需要计算很多次f（1）、f（2）

　　递归版本的 f 函数是一个指数级复杂度的算法

　　迭代使用三个变量 f(n - 1), f(n - 2), f(n - 3) 的值，使用自底向上的计算方式进行计算，因此迭代版本没有多余的重复计算工作，它的复杂度正比n，是一个线性迭代函数。

练习 1.12

　　　　　　　 　　　1　　

　　　　　　　　　1　　1

　　　　　　　　1　　2　　1

　　　　　　  1　　3　　3　　1

　　　　　 1　　4　　 6　　4　　1

　　　　　　　      。。。。。

Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

三角形边界的数都是1，内部的每个数是位于它上面的两个数之和。

请写一个过程，采用递归计算过程 计算出帕斯卡三角形的各个元素。

答案：

　　(define (Pascal n)

　　　　(cond (= (/ n 2) 0)

　　　　　　　((= n 2)

　　(define (Pascal x y)

　　　　(+ (Pascal (- x 1) (- y 1)) (Pascal (- x 1) y)

　　解题集：

　　如果使用 pascal(row, col) 代表第 row 行和第 col 列上的元素的值，可以得出一些性质：

• • 　　每个 pascal(row, col) 由 pascal(row-1, col-1) (左上边的元素)和pascal(row-1, col) (右上边的元素)组成。
  • 　　当 col 等于 0 (最左边元素)，或者 row 等于 col (最右边元素)时， pascal(row, col) 等于 1。

　　比如说，当 row = 3 ， col = 1 时， pascal(row,col) 的值为 3 ，而这个值又是根据 　　　　pascal(3-1, 1-1) = 1 和 pascal(3-1, 1) = 2 计算出来的。

综合以上的两个性质，就可以写出递归版本的 pascal 函数了：

(define (pascal row col)
    (cond ((> col row)
                (erroe "unvalid col value"))
             ((or (= col ) (= row col))
                 )
             () (- col ))
                          (pascal (- row ) col)))))

前面给出的递归版本 pascal 函数的效率并不好，首先，因为它使用的是递归计算方式，所以它的递归深度受限于解释器所允许的最大递归深度。

其次，递归版本 pascal 函数计算值根据的是公式 这个公式带有重复计算，并且复杂度也很高，因此，前面给出的 pascal 函数只能用于 row 和 col 都非常小的情况。

要改进这一状况，可以使用帕斯卡三角形的另一个公式来计算帕斯卡三角形的元素

，其中表示的阶乘(factorial)

阶乘：factorial（跌代版）

(define (factorial n)

　　(fact-iter 1 1 n))

(define (fact-iter product counter max-count)

　　(if (> counter max-count)

　　　　product

　　　　(fact-iter (* counter product)

　　　　　　　　　(+ counter 1)

　　　　　　　　　max-count)))

跌代版的pascal定义：

　　(define (pascal row col)

　　　　(/ (factorial row)

　　　　　 (* (factorial col)

　　　　　　　(factorial (- row col)))))

迭代版的 pascal 函数消除了递归版 pascal 的重复计算，并且它是一个线性复杂度的算法

因此，

迭代版的 pascal 比起递归版的 pascal 要快不少，并且计算的值的大小不受递归栈深度的控制：

1.2.3 增长的阶　　

目的：描述不同的计算过程在消耗资源的速率上可能存在着巨大差异。

计算阶乘：   计算过程所需步骤的增长　　　　   空间需求的增长

　　递归： 　　     　O（n）　　　　　   　　      O（n）

　　迭代：　　      　O（n）　　　　　　   　　　O（1）（即为一个常数） 　　

斐波那契计算

树形递归　 　O（黄金分割率的 n 次方） 　 　　　O（n）

练习1.15

a:

p是翻译的定义，限制为(> (abs angle) 0.1))

每递归一次，angle \ 3.0

12.15 \  3.0

4.05

1.35

0.45

0.15

0.05

五次

b:

在求值（sine a）的时候，a每次都被除以 3.0 ， 而sine是一个递归程序，因此它的时间和空间复杂度都是 O(log a)。 （由O(log3(a/0.033333 = log3(30a) = log3(30) + log3(a), log3(30)是常数，因此是O(log a)

即每当 a 增大一倍（准确的说是乘因子 3），p的运行次数就会增加一次。

1.2.4 求幂