c語言高級編程[1]

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

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

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

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

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

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