Posted on 2007-05-09 14:57
dennis 阅读(1275)
评论(2) 编辑 收藏 所属分类:
计算机科学与基础
这个小节主要讲解了迭代与树形递归，递归比起迭代更易于理解和直观，而迭代相比于递归则效率更高，一般计算机的递归实现都是使用堆栈结构实现的，当递归层次太深的时候容易导致栈溢出，而迭代则没有这样的问题。
习题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))))))