編寫遞歸程序有幾個(gè)重要的原則可以遵循

1、編寫遞歸程序有幾個(gè)重要的原則可以遵循：.要解決的問(wèn)題可拆分為幾個(gè)與原問(wèn)題類似 的子問(wèn)題（子問(wèn)題仍可拆分）。.每個(gè)子問(wèn)題必須比原來(lái)問(wèn)題的規(guī)模更小（即使小一號(hào)也行，當(dāng)然如果能夠迅速減小規(guī)模更好）。.遇到足夠小的子問(wèn)題時(shí)就直接解決之，防止問(wèn)題無(wú)限細(xì)分下去，也就是防止無(wú)限遞歸（遞歸終止條件很重要）。先看一個(gè)最簡(jiǎn)單的遞歸程序，下面程序求整數(shù)的階乘：( ) ? : *();所謂遞歸程序，就是程序在執(zhí)行中又調(diào)用其自身，如上面函數(shù)在其函數(shù)體內(nèi)調(diào)用了函數(shù)。函數(shù)在每次被調(diào)用時(shí)都會(huì)生成一個(gè)包含自身局部變量的副本，即算是函數(shù)調(diào)用自身時(shí)也是如此。遞歸程序主體主要由兩部分構(gòu)成：一是遞歸執(zhí)行部分，包含遞歸執(zhí)行所需的條件；一

2、是遞歸終止部分，含遞歸終止條件。上面求階乘的程序中把這兩部分寫在一行代碼里面，把其分別抽出來(lái)便是：( )( ) ;遞歸終止體*();遞歸執(zhí)行體下面以幾個(gè)經(jīng)典算法問(wèn)題的遞歸程序求解為例來(lái)分析編寫遞歸程序中可以遵循的簡(jiǎn)單規(guī)則。. 求正整數(shù)所有可能的和式的組合，如給定正整數(shù)，所有和加起來(lái)等于的和式如下：其中一個(gè)和式中的因子只能為自然數(shù)，因子允許重復(fù)出現(xiàn)。這個(gè)問(wèn)題是一個(gè)組合問(wèn)題的變形，用遞歸程序?qū)崿F(xiàn)如下（分析見(jiàn)注釋）：;存儲(chǔ)和式因子組合的緩沖求當(dāng)前和式中因子之和。1 / 14( );( ; ; );打印當(dāng)前滿足條件的和式。( ), ;(; ; )注意這里的循環(huán)條件，可以有效防止出現(xiàn)重復(fù)的組合 ;( (

3、)首先要確定遞歸中止條件();( )和式中的因子不應(yīng)該超過(guò)和的大小;();減小問(wèn)題規(guī)模，繼續(xù)遞歸;()2 / 14;(:);();();. 給定正整數(shù)，以及共 個(gè)正整數(shù)的一個(gè)排列， 假如是 ，. ，求所有和此排列 “不相交 ”的排列。所謂不相交，是指新的排列和已有排列在同一位置上的數(shù)都不相同。如假設(shè)，則其排列：和是相交的，因?yàn)榈诙€(gè)位置上都是；而排列和則不相交。問(wèn)題分析： 此問(wèn)題是普通排列問(wèn)題的變形， 只要在排列問(wèn)題的遞歸程序中加上位置的限制即可，程序?qū)崿F(xiàn)如下，具體分析見(jiàn)注釋。; ;預(yù)定義好位置的排列判斷當(dāng)前選擇的數(shù)是否已經(jīng)被使用。( , * )( ; ; )();求不相交排列。當(dāng)前排列的位置

4、或者說(shuō)當(dāng)前排列元素個(gè)數(shù)。存儲(chǔ)當(dāng)前排列的數(shù)組。存儲(chǔ)不相交排列的數(shù)目。( , * , )( )遞歸終止條件( ; ; ) ; ;3 / 14( ; ; )循環(huán)挑選當(dāng)前位置可以放置的數(shù)()判斷當(dāng)前選定的數(shù)是夠已經(jīng)用過(guò); ;( )回溯的限制條件，同一位置的數(shù)不能和預(yù)定義的排列中相應(yīng)位置的數(shù)相同;();繼續(xù)遞歸 ;回溯，重新初始化當(dāng)前位置() ;(); ;遞歸程序求解問(wèn)題雖然優(yōu)美簡(jiǎn)潔，但是和相應(yīng)的非遞歸程序比較，隨著問(wèn)題規(guī)模的增大，程序的效率會(huì)逐漸下降，這也是遞歸程序的一大缺陷盡管排列組合是生活中經(jīng)常遇到的問(wèn)題，可在程序設(shè)計(jì)時(shí)，不深入思考或者經(jīng)驗(yàn)不足都讓人無(wú)從下手。由于排列組合問(wèn)題總是先取組合再排列，并

5、且單純的排列問(wèn)題相對(duì)簡(jiǎn)單，所以本文僅對(duì)組合問(wèn)題的實(shí)現(xiàn)進(jìn)行詳細(xì)討論。以在個(gè)數(shù)中選取 ( 。用來(lái)存儲(chǔ)當(dāng)前組合中的元素( 這里存儲(chǔ)的是元素下標(biāo)) ，常量表示滿足條件的一個(gè)組合中元素的個(gè)數(shù)，這兩個(gè)參數(shù)僅用來(lái)輸出結(jié)果。( , , ,)( ; ; )注意這里的循環(huán)范圍;( )();,輸出一個(gè)組合( ; ; ) ; ;因?yàn)檫f歸程序均可以通過(guò)引入棧，用回溯轉(zhuǎn)化為相應(yīng)的非遞歸程序，所以組合問(wèn)題又可以用回溯的方法來(lái)解決。為了便于理解，我們可以把組合問(wèn)題化歸為圖的路徑遍歷問(wèn)題，在個(gè)數(shù)中選取個(gè)數(shù)的所有組合，相當(dāng)于在一個(gè)這樣的圖中（下面以從中任選個(gè)數(shù)為例說(shuō)明）求從 位置出發(fā)到達(dá) ( ? : ;5 / 14*;( ; ;

6、 ) ;注意這里 用來(lái)作為循環(huán)判斷標(biāo)識(shí);標(biāo)志找到一個(gè)有效組合( )()輸出符合要求的組合(; ; ) ; ;在當(dāng)前位置選擇新的數(shù)字( )當(dāng)前位置已無(wú)數(shù)字可選，回溯 ;( )更新當(dāng)前位置的下一位置的數(shù)字 ;( ); ;下面是測(cè)試以上函數(shù)的程序：();6 / 14;( ) ;回溯方法 () ;遞歸方法;();由上述分析可知， 解決組合問(wèn)題的通用算法不外乎遞歸和回溯兩種。在針對(duì)具體問(wèn)題的時(shí)候，因?yàn)檫f歸程序在遞歸層數(shù)上的限制， 對(duì)于大型組合問(wèn)題而言， 遞歸不是一個(gè)好的選擇， 這種情況下只能采取回溯的方法來(lái)解決。個(gè)數(shù)的全排列問(wèn)題相對(duì)簡(jiǎn)單，可以通過(guò)交換位置按序枚舉來(lái)實(shí)現(xiàn)。提供了求某個(gè)序列下一個(gè)排列的算法，

7、其算法原理如下：. 從當(dāng)前序列最尾端開始往前尋找兩個(gè)相鄰元素，令前面一個(gè)元素為*，后一個(gè)元素為*，且滿足 * ；. 再次從當(dāng)前序列末端開始向前掃描，找出第一個(gè)大于*的元素，令為*（可能等于），將，元素對(duì)調(diào)；. 將之后（含）的所有元素顛倒次序，這樣所得的排列即為當(dāng)前序列的下一個(gè)排列。其實(shí)現(xiàn)代碼如下：( , )( ) ;空範(fàn)圍;( ) ;只有一個(gè)元素;指向尾端;(;);以上，鎖定一組（兩個(gè)）相鄰元素(* *)如果前一個(gè)元素小於後一個(gè)元素7 / 14;令 指向尾端(!(* *);由尾端往前找，直到遇上比*大的元素(, );交換 ,(, );將之後的元素全部逆向重排;( )進(jìn)行至最前面了(, );全部

8、逆向重排;下面程序演示了利用來(lái)求取某個(gè)序列全排列的方法：() ; ()();()()(, ); ;()()()()(, ); ;注意： 上面程序中初始序列是按數(shù)值的從小到大的順序排列的，如果初始序列無(wú)序的話，上面程序只能求出從當(dāng)前序列開始的后續(xù)部分排列，也就是說(shuō)求出的排列是按排列從小到大的順序進(jìn)行的。最優(yōu)化原理年美國(guó)數(shù)學(xué)家等人，根據(jù)一類多階段問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題變換為一系列互相聯(lián)系的單階段問(wèn)題，然后逐個(gè)加以解決。一些靜態(tài)模型，只要人為地引進(jìn) “時(shí)間 ”因素，分成時(shí)段， 就可以轉(zhuǎn)化成多階段的動(dòng)態(tài)模型， 用動(dòng)態(tài)規(guī)劃方法去處理。 與此同時(shí)， 他提出了8 / 14解決這類問(wèn)題的“最優(yōu)化原理 ”

9、()：“一個(gè)過(guò)程的最優(yōu)決策具有這樣的性質(zhì)：即無(wú)論其初始狀態(tài)和初始決策如何，其今后諸策略對(duì)以第一個(gè)決策所形成的狀態(tài)作為初始狀態(tài)的過(guò)程而言，必須構(gòu)成最優(yōu)策略”。簡(jiǎn)言之，一個(gè)最優(yōu)策略的子策略，對(duì)于它的初態(tài)和終態(tài)而言也必是最優(yōu)的。這個(gè) “最優(yōu)化原理 ”如果用數(shù)學(xué)化一點(diǎn)的語(yǔ)言來(lái)描述的話， 就是：假設(shè)為了解決某一優(yōu)化問(wèn)題，需要依次作出個(gè)決策， ，如若這個(gè)決策序列是最優(yōu)的，對(duì)于任何一個(gè)整數(shù)， ，不論前面?zhèn)€決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài)，即以后的決策， ，也是最優(yōu)的。最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)。任何一個(gè)問(wèn)題，如果失去了這個(gè)最優(yōu)化原理的支持，就不可能用動(dòng)態(tài)規(guī)劃方法計(jì)算。能采用動(dòng)態(tài)

10、規(guī)劃求解的問(wèn)題都需要滿足一定的條件：()問(wèn)題中的狀態(tài)必須滿足最優(yōu)化原理；()問(wèn)題中的狀態(tài)必須滿足無(wú)后效性。所謂的無(wú)后效性是指：“下一時(shí)刻的狀態(tài)只與當(dāng)前狀態(tài)有關(guān)，而和當(dāng)前狀態(tài)之前的狀態(tài)無(wú)關(guān)，當(dāng)前的狀態(tài)是對(duì)以往決策的總結(jié)”。問(wèn)題求解模式動(dòng)態(tài)規(guī)劃所處理的問(wèn)題是一個(gè)多階段決策問(wèn)題，一般由初始狀態(tài)開始，通過(guò)對(duì)中間階段決策的選擇， 達(dá)到結(jié)束狀態(tài)。 這些決策形成了一個(gè)決策序列， 同時(shí)確定了完成整個(gè)過(guò)程的一條活動(dòng)路線 ( 通常是求最優(yōu)的活動(dòng)路線 ) 。如圖所示。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟。初始狀態(tài) 決策 決策 決策 結(jié)束狀態(tài)圖 動(dòng)態(tài)規(guī)劃決策過(guò)程示意圖()劃分階段：按照問(wèn)題的時(shí)間或空

11、間特征，把問(wèn)題分為若干個(gè)階段。在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問(wèn)題就無(wú)法求解。()確定狀態(tài)和狀態(tài)變量：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。當(dāng)然，狀態(tài)的選擇要滿足無(wú)后效性。()確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。 所以如果確定了決策， 狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過(guò)來(lái)做，根據(jù)相鄰兩段各狀態(tài)之間的關(guān)系來(lái)確定決策。()尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。算法實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，也就是上

12、面?zhèn)€步驟的確定，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。使用動(dòng)態(tài)規(guī)劃求解問(wèn)題，最重要的就是確定動(dòng)態(tài)規(guī)劃三要素：?jiǎn)栴}的階段 , 每個(gè)階段的 狀態(tài) 以及從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系 。遞推關(guān)系必須是從次小的問(wèn)題開始到較大的問(wèn)題之間的轉(zhuǎn)化，從這個(gè)角度來(lái)說(shuō)， 動(dòng)態(tài)規(guī)劃往往可以用遞歸程序來(lái)實(shí)現(xiàn)， 不過(guò)因?yàn)檫f推可以充分利用前面保存的子問(wèn)題的解來(lái)減少重復(fù)計(jì)算，所以對(duì)于大規(guī)模問(wèn)題來(lái)說(shuō)，有遞歸不可比擬的優(yōu)勢(shì)，這也是動(dòng)態(tài)規(guī)劃算法的核心之處。確定了動(dòng)態(tài)規(guī)劃的這三要素， 整個(gè)求解過(guò)程就可以用一個(gè)最優(yōu)決策表 來(lái)描述，最優(yōu)決策表是一個(gè)二維表，9 / 14其中行表示決策的階段， 列表示問(wèn)題狀態(tài)， 表格需要填寫的數(shù)

13、據(jù)一般對(duì)應(yīng)此問(wèn)題的在某個(gè)階段某個(gè)狀態(tài)下的最優(yōu)值（如最短路徑，最長(zhǎng)公共子序列，最大價(jià)值等），填表的過(guò)程就是根據(jù)遞推關(guān)系，從行列開始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據(jù)整個(gè)表格的數(shù)據(jù)通過(guò)簡(jiǎn)單的取舍或者運(yùn)算求得問(wèn)題的最優(yōu)解。 下面分別以求解最大化投資回報(bào)問(wèn)題和最長(zhǎng)公共子序列問(wèn)題為例闡述用動(dòng)態(tài)規(guī)劃算法求解問(wèn)題的一般思路。.最大化投資回報(bào)問(wèn)題：某人有一定的資金用來(lái)購(gòu)買不同面額的債卷，不同面額債卷的年收益是不同的， 求給定資金， 年限以及債卷面額、 收益的情況下怎樣購(gòu)買才能使此人獲得最大投資回報(bào)。程序輸入約定：第一行第一列表示資金（的倍數(shù)）總量，第二列表示投資年限；第二行表示債卷面額總數(shù)；從第三

14、行開始每行表示一種債卷，占用兩列，前一列表示債卷面額，后一列表示其年收益，如下輸入實(shí)例，程序?qū)崿F(xiàn)如下，注釋幾乎說(shuō)明了一切，所以不再另外分析。此數(shù)組是算法的關(guān)鍵存儲(chǔ)結(jié)構(gòu)，用來(lái)存儲(chǔ)不同階段各種債卷組合下對(duì)應(yīng)可獲取的最大利息。;此函數(shù)用于計(jì)算當(dāng)前債卷在不同購(gòu)買額下的最優(yōu)利息情況，注意此時(shí)的利息情況是基于上一次債卷的情況下計(jì)算得到的，也就是說(shuō)當(dāng)前利息最優(yōu)是基于上一次利息最優(yōu)的基礎(chǔ)上計(jì)算出來(lái)的，這也正好體現(xiàn)了動(dòng)態(tài)規(guī)劃中 “最優(yōu)化原則 ”：不管前面的策略如何，此后的決策必須是基于當(dāng)前狀態(tài)（由上一次決策產(chǎn)生）的最優(yōu)決策。*動(dòng)態(tài)規(guī)劃的求解過(guò)程一般都可以用一個(gè)最優(yōu)決策表來(lái)描述，對(duì)于本程序，以示例輸入為例，對(duì)于第

15、一年，其最優(yōu)決策表如下：(*)()()()()表示首先選利息為的債卷在對(duì)應(yīng)資金下的最優(yōu)利息。()表示可用來(lái)購(gòu)買債卷的資金。()表示在已有狀態(tài)下再選擇利息為的債卷在對(duì)應(yīng)資金下的最優(yōu)利息。注意上面表格，在求購(gòu)買利息為的債卷獲得的最優(yōu)收益的時(shí)候，參考了以前的最優(yōu)狀態(tài)，以行列的為例，(*)可以在以前購(gòu)買了張的債卷的基礎(chǔ)上再?gòu)埖?，也可以在以前?gòu)買了張的基礎(chǔ)上再買張，經(jīng)比較取其收益大的，這就是典型的動(dòng)態(tài)規(guī)劃中的當(dāng)前最優(yōu)狀態(tài)計(jì)算。本程序中把上面的最優(yōu)決策二維表用一個(gè)一維數(shù)組表示，值得借鑒。*10 / 14( ) ; ( );( )累計(jì)同時(shí)購(gòu)買多種債卷時(shí)的利息 ;() ; ;();();()();();();()();();計(jì)算指定年限內(nèi)最優(yōu)組合的本金利息