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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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