195
用遞歸計算階乘咋不行呢？
讀《代碼大全2》，已經讀了一半，喘口氣。總結八個字：百科全書，受益匪淺。小到一個賦值語句、一個循環的編寫，大到需求分析、架構設計，無所不包，看後半部分目錄，更是扯到了重構、軟件工藝、程序員的性格特征這樣的話題。恰好手邊的工作暫時比較有閑，可以實踐下“創建高質量的代碼”中的部分建議，晚上讀書，第二天就重構，樂在其中。這一部分中對設計、子程序、類、變量、語句的處理建議，可能你平常已經在這麼做，可作者這麼精辟地概括出來讓人歎服，而有些地方是你平常絕對很少注意的，特別是在變量和三種常見控製語句的處理上。說說我認為是缺點的地方，就是作者貌似對函數式語言了解很少，舉的例子全部用的是廣泛應用的靜態語言（c/c++,java,vb)。例如作者有這麼一句話：如果為我工作的程序員用遞歸去計算階乘，那麼我寧願換人。作者對遞歸的態度相當謹慎，這在靜態命令式語言中顯然是正確的，但是在函數式語言中，由於有尾遞歸優化的存在，遞歸反而是最自然的形式，況且我打心裏認為遞歸更符合人類思維。請注意，在FP中隻有尾遞歸的程序才是線性迭代的，否則寫出來的遞歸可能是線性遞歸或者樹形遞歸，兩種情況下都可能導致堆棧溢出並且性能較差。
scheme寫階乘：
(define (fac n)
(if (= 1 n)
1
(* n (fac (- n 1)))))
顯然這個版本不是尾遞歸，計算過程是一個線性遞歸過程，計算(fac 4)的過程如下：(if (= 1 n)
1
(* n (fac (- n 1)))))
(* 4 （fac 3))
(* 4 (3 * (fac 2)))
(* 4 (3 * (* 2 (fac 1))))
(* 4 (3 * (* 2 1)))
(* 4 (3 * 2))
(* 4 6)
24
因為解釋器是采用應用序求值，需要將表達式完全展開，然後依次求值，在這個過程中，解釋器內部需要保存一條長長的推遲計算的軌跡。
改寫成一個尾遞歸版本：
(define (fac n)
(define (fac-iter product n)
(if (= 1 n)
product
(fac-iter (* n product) (- n 1))))
(fac-iter 1 n))
我們來看看它的計算過程：(define (fac-iter product n)
(if (= 1 n)
product
(fac-iter (* n product) (- n 1))))
(fac-iter 1 n))
(fac-iter 1 4)
(fac-iter 4 3)
(fac-iter 12 2)
(fac-iter 24 1)
24
可以看到，在這個過程中，解釋器不需要保存計算軌跡，迭代的中間結果通過product變量來保存，這是一個線性迭代的計算過程。
最後再看一個斐波拉契數列的例子：
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else
(+ (fib (- n 1)) (fib (- n 2))))))
(cond ((= n 0) 0)
((= n 1) 1)
(else
(+ (fib (- n 1)) (fib (- n 2))))))
這個計算過程展開是一個樹形遞歸的過程(為什麼說是樹形？展開下計算過程就知道），改寫為線性迭代：
(define (fib n)
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
(fib-iter 1 0 n))
上述的內容在sicp第一章裏有更詳細的介紹和討論。
文章轉自莊周夢蝶 ，原文發布時間 2008-03-18
最後更新：2017-05-17 17:32:09