sicp 1.11 1.12习题解答

    这个小节主要讲解了迭代与树形递归，递归比起迭代更易于理解和直观，而迭代相比于递归则效率更高，一般计算机的递归实现都是使用堆栈结构实现的，当递归层次太深的时候容易导致栈溢出，而迭代则没有这样的问题。
习题1.11是这样的：
    如果n<3，那么f(n)=n;如果n>=3，那么f(n)=f(n-1)+2f(n-2)+3f(n-3)，请写一个采用递归计算过程f的过程，再改写一个采用迭代计算过程计算f的过程。

解答：
1.采用递归的话就很简单了，可以将条件直接描述为一个lisp过程，没什么好解释的：

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

2。迭代就相对麻烦点，将递归转化为迭代，关键在于找出迭代每一步之间的差异，这个差异就是每次迭代变化的量，找出这个固定编号的量就是问题的关键。很容易就可以看出f(n)和f(n-1)之间的差距就是：2f(n-2)+3f(n-3)。这就提示我们需要保持3个顺序的状态变量：f(n-2)、 f(n-1) 、f(n)，迭代向前一步的时候：f(n-2)被f(n-1)取代，f(n-1)被f(n)取代，将f(n)+2f(n-2)+3f(n-3)做为新的f(n)。迭代是自底向上，初始化的3个变量就是0、1、2，这样就可以相应地写出一个迭代版本的解答：

<!---->(define (f-iter a b c n)
          (if (= n 2)
              c
              (f-iter b c (+ c (* 2 b) (* 3 a)) (- n 1))))
(define (f-i n) (f-iter 0 1 2 n))

可以测试一下，在n数目比较大的时候，递归版本速度明显变慢甚至栈溢出，而迭代版本就比较快了。

习题1.12：用递归过程描述帕斯卡三角（或者说杨辉三角）
根据杨辉三角的特点，x行y列的数字等于x-1行y列的数字和x-1行y-1列的数字之和，就可以解决这个问题：

<!---->(define (pascal x y)
        (cond ((> y x) (display "error"))
              ((= x 1) 1)
              ((= x 2) 1)
              ((= y 1) 1)
              ((= x y) 1)
              (else 
              (+ (pascal (- x 1) y) (pascal (- x 1) (- y 1))))))

dennis 2007-05-09 14:57 发表评论