Posted on 2007-05-09 14:57
dennis 閱讀(1292)
評論(2) 編輯 收藏 所屬分類:
計算機科學與基礎
這個小節(jié)主要講解了迭代與樹形遞歸，遞歸比起迭代更易于理解和直觀，而迭代相比于遞歸則效率更高，一般計算機的遞歸實現(xiàn)都是使用堆棧結(jié)構(gòu)實現(xiàn)的，當遞歸層次太深的時候容易導致棧溢出，而迭代則沒有這樣的問題。
習題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。迭代就相對麻煩點，將遞歸轉(zhuǎn)化為迭代，關鍵在于找出迭代每一步之間的差異，這個差異就是每次迭代變化的量，找出這個固定編號的量就是問題的關鍵。很容易就可以看出f(n)和f(n-1)之間的差距就是：2f(n-2)+3f(n-3)。這就提示我們需要保持3個順序的狀態(tài)變量：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數(shù)目比較大的時候，遞歸版本速度明顯變慢甚至棧溢出，而迭代版本就比較快了。
習題1.12：用遞歸過程描述帕斯卡三角（或者說楊輝三角）根據(jù)楊輝三角的特點，x行y列的數(shù)字等于x-1行y列的數(shù)字和x-1行y-1列的數(shù)字之和，就可以解決這個問題：
(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))))))