c語言高級編程[1]

1、Comment[創(chuàng)創(chuàng)1]:頁：237C語言高級編程技術(shù)237C語言高級編程技術(shù)語言高級編程技術(shù)8.18.1遞歸程序設計遞歸程序設計8.1.18.1.1遞歸與遞歸程序設計遞歸與遞歸程序設計遞歸技術(shù)在算法和程序設計中是一種十分有用的技術(shù)，C語言提供了支持遞歸定義的機制和手段。遞歸有直接遞歸和間接遞歸兩種。在一個函數(shù)的定義中出現(xiàn)了對自身的調(diào)用，稱之為直接遞歸；一個函數(shù)f的定義中包含了對函數(shù)g的調(diào)用，而g的實現(xiàn)過程又調(diào)用了f，即函數(shù)調(diào)用形成了一

2、個環(huán)狀調(diào)用鏈這種方式稱之為間接遞歸。例8.18.1編寫一個遞歸函數(shù)，求n的階乘值n！。若用fact(n)表示n的階乘值，根據(jù)階乘的數(shù)學定義可知：????????0)1(01)(nnfactnnnfact顯然當n0時，fact(n)是建立在fact(n1)的基礎(chǔ)上。由于求解fact(n1)的過程與求解fact(n)的過程完全相同，只是具體實參不同，因而在進行程序設計時，不必再仔細考慮fact(n1)的具體實現(xiàn)，只需借助遞歸機制進行自身調(diào)用

3、即可。于是求n的階乘值fact(n)的具體實現(xiàn)為：longfact(intn)longmif(n==0)return(1)elsem=nfact(n1)return(m)例8.28.2編寫一個遞歸函數(shù)，求Fibonacci數(shù)列第n項的值。若用Fibona(n)表示Fibonacci數(shù)列第n項的值，根據(jù)Fibonacci數(shù)列的計算公式：???????2n2)Fibona(n1)Fibona(n211Fibona(n)n可知當n2時，F(xiàn)ib

4、onacci數(shù)列第n項的值等于第n1項的值與第n2項的值相加之和，而Fibonacci數(shù)列第n1項和第n2項值的求解又分別取決于它們各自前兩項之和?？傊?，F(xiàn)ibona(n1)和Fibona(n2)的求解過程與Fibona(n)的求解過程相同，只是具體實參不同。利用以上這種性質(zhì)，我們在進行程序設計時便可以使用遞歸技術(shù)，F(xiàn)ibona(n1)和Fibona(n2)C語言高級編程技術(shù)239調(diào)用，這樣逐層返回，直至返回到第一次調(diào)用，當?shù)谝淮握{(diào)用結(jié)

5、束后，釋放調(diào)用所分配的空間，整個遞歸調(diào)用才完成。在例8.1中，給出了一個求階乘的函數(shù)。下面以求4!為例，其調(diào)用過程如圖81所示。要求4!即要求的fact(4)值。圖81遞歸函數(shù)調(diào)用的執(zhí)行過程8.1.38.1.3遞歸算法的優(yōu)缺點遞歸算法的優(yōu)缺點遞歸函數(shù)的主要優(yōu)點是可以把算法寫的比使用非遞歸函數(shù)時更清晰更簡潔，而且某些問題，特別是與人工智能有關(guān)的問題，更適宜用遞歸方法。遞歸算法的缺點，一是需要額外的內(nèi)存開銷，特別是當遞歸層次較大時，遞歸函數(shù)

6、需要占用的堆?？臻g相當大。二是遞歸引起一系列的函數(shù)調(diào)用，并且可能會有一系列的重復計算，遞歸算法的執(zhí)行效率相對較低?？傊?，遞歸算法要比解決同樣問題的非遞歸算法效率低一些。內(nèi)存空間需求更多一些。大多數(shù)用遞歸算法解決的問題，都可以找到相應的非遞歸算法，只有少數(shù)問題的求解只有遞歸算法。由于遞歸算法具有效率低、內(nèi)存消耗大等缺點，在設計程序時，若有比較好的非遞歸算法，應盡量采用非遞歸算法。8.1.48.1.4遞歸程序設計的應用實例遞歸程序設計的應用