练习1.12

采用如下递推式：

$Pascal(x,y)=\left\{ \begin{array}{ll} 1,&\text{y = 0 or y = x}\\ Paxcal(x-1,y-1)+Pascal(x-1,y),&\text{other cases} \end{array}\right.$

根据递推式，就可以写出如下递归版本的Pascal计算过程

(define (pascal x y)
    (cond ((or (= y 0) (= y x)) 1)
          (else (+ (pascal (- x 1) (- y 1)) (pascal (- x 1) y)))))

这个过程带有大量冗余的计算 十分容易导致栈溢出 效率也很低下

根据Pascal三角形的通项公式 可以使用迭代的方法进行计算

$Pascal(x,y)=C^{y}_{x}={x!\over{y!(x-y)!}}$

阶乘可以使用书本22页提供的迭代版计算过程

(define (factorial n)
    (define (fact-iter product counter max-count)
        (if (> counter max-count)
            product
            (fact-iter (* counter product)
                    (+ counter 1)
                    max-count)))
    (fact-iter 1 1 n))

(define (iter-pascal x y)
    (/ (factorial x)
       (* (factorial y)
          (factorial (- x y)))))

这个版本的时间复杂度和空间复杂度都有大幅度改进