函數(shù)的遞歸調(diào)用與分治策略

1、函數(shù)的遞歸調(diào)用與分治策略遞歸方法是算法和程序設(shè)計中的一種重要技術(shù)。遞歸方法即通過函數(shù)或過程調(diào)用自身將問題轉(zhuǎn)化為本質(zhì)相同但規(guī)模較小的子問題。遞歸方法具有易于描述和理解、證明簡單等優(yōu)點，在動態(tài)規(guī)劃、貪心算法、回溯法等諸多算法中都有著極為廣泛的應(yīng)用，是許多復(fù)雜算法的基礎(chǔ)。遞歸方法中所使用的“分而治之”的策略也稱分治策略。遞歸方法的構(gòu)造構(gòu)造遞歸方法的關(guān)鍵在于建立遞歸關(guān)系。這里的遞歸關(guān)系可以是遞歸描述的，也可以是遞推描述的。下面由一個求n的階乘的程序為例，總結(jié)出構(gòu)造遞歸方法的一般步驟。例1從鍵盤輸入正整數(shù)N（0<=N<=20），輸出N!。分析N!的計算是一個典型的遞歸問題。使用遞歸方法來描述

2、程序，十分簡單且易于理解。步驟1描述遞歸關(guān)系 遞歸關(guān)系是這樣的一種關(guān)系。設(shè)U1,U2,U3,Un是一個序列，如果從某一項k開始，Un和它之前的若干項之間存在一種只與n有關(guān)的關(guān)系，這便稱為遞歸關(guān)系。注意到，當(dāng)N>=1時，N!=N*(N-1)!（N=1時，0!=1），這就是一種遞歸關(guān)系。對于特定的K!，它只與K與(K-1)!有關(guān)。步驟2確定遞歸邊界 在步驟1的遞歸關(guān)系中，對大于k的Un的求解將最終歸結(jié)為對Uk的求解。這里的Uk稱為遞歸邊界（或遞歸出口）。在本例中，遞歸邊界為k=0，即0!=1。對于任意給定的N!，程序?qū)⒆罱K求解到0!。確定遞歸邊界十分重要，如果沒有確定遞歸邊界，將導(dǎo)致程序無限

3、遞歸而引起死循環(huán)。例如以下程序：#include <iostream.h>int f(int x) return(f(x-1);main() cout<<f(10);它沒有規(guī)定遞歸邊界，運行時將無限循環(huán)，會導(dǎo)致錯誤。步驟3寫出遞歸函數(shù)并譯為代碼 將步驟1和步驟2中的遞歸關(guān)系與邊界統(tǒng)一起來用數(shù)學(xué)語言來表示，即 N*(N-1)! 當(dāng)N>=1時n!= 1 當(dāng)N=0時再將這種關(guān)系翻譯為代碼，即一個函數(shù)：long f(int n) if (n=0) return(1); else return(n*f(n-1);步驟4完善程序 主要的遞歸函數(shù)已經(jīng)完成，將程序依題意補充完整即

4、可。/ex1.cpp#include <iostream.h>long f(int n) if (n=0) return(1); else return(n*f(n-1);main() int n; cin>>n; cout<<endl<<f(n);綜上，得出構(gòu)造一個遞歸方法基本步驟，即描述遞歸關(guān)系、確定遞歸邊界、寫出遞歸函數(shù)并譯為代碼，最后將程序完善。以下繼續(xù)引用一些例子來討論遞歸方法的應(yīng)用。經(jīng)典遞歸問題以下討論兩個十分經(jīng)典的遞歸問題。它們的算法構(gòu)造同樣遵循剛剛得出的四個步驟。了解這兩個問題可加深對遞歸方法的理解。例2Fibonacci數(shù)列（兔

5、子繁殖）問題：已知無窮數(shù)列A，滿足：A(1)=A(2)=1，A(N)=A(N-1)+A(N-2)（N>=3）。從鍵盤輸入N，輸出A(N)。分析遞歸關(guān)系十分明顯，由A(N)的表達式給出。需要注意的是本例中對于N>=3，A(N)的值與A(N-1)和A(N-2)都有關(guān)。代碼/ex2.cpp#include <iostream.h>long fibonacci(int x) if ( (x=1) | (x=2) ) return(1); else return(fibonacci(x-1)+fibonacci(x-2);main() int n; cin>>n; c

6、out>>endl>>fibonacci(n); 例3Hanoi塔問題。 問題描述在霍比特人的圣廟里，有一塊黃銅板，上面插著3根寶石針（分別為A號，B號和C號）。在A號針上從下到上套著從大到小的n個圓形金片?，F(xiàn)要將A針上的金片全部移到C針上，且仍按照原來的順序疊置。移動的規(guī)則如下：這些金片只能在3根針間移動，一次只能一片，且任何時候都不允許將較大的金片壓在較小的上面。從鍵盤輸入n，要求給出移動的次數(shù)和方案。分析由金片的個數(shù)建立遞歸關(guān)系。當(dāng)n=1時，只要將唯一的金片從A移到C即可。當(dāng)n>1時，只要把較小的(n-1)片按移動規(guī)則從A移到B，再將剩下的最大的從A移到C（

7、即中間“借助”B把金片從A移到C），再將B上的(n-1)個金片按照規(guī)則從B移到C（中間“借助”A）。本題的特點在于不容易用數(shù)學(xué)語言寫出具體的遞歸函數(shù)，但遞歸關(guān)系明顯，仍可用遞歸方法求解。代碼/ex3.cpp#include <iostream.h>hanoi(int n,char t1,char t2,char t3) if (n=1) cout<<"1 "<<t1<<" "<<t3<<endl; else hanoi(n-1,t1,t3,t2); cout<<n<

8、<" "<<t1<<" "<<t3<<endl; hanoi(n-1,t2,t1,t3); main() int n; cout<<"Please enter the number of Hanoi:" cin>>n; cout<<"Answer:"<<endl; hanoi(n,'A','B','C');函數(shù)遞歸調(diào)用的應(yīng)用與分治策略許多算法都采用了分治策略求解，而可

9、以說分治與遞歸是一對孿生兄弟，它們經(jīng)常同時被應(yīng)用于算法的設(shè)計中。下面討論著名的Catalan數(shù)問題，人們在對它的研究中充分應(yīng)用了分治策略。例4Catalan數(shù)問題。問題描述一個凸多邊形，通過不相交于n邊形內(nèi)部的對角線，剖分為若干個三角形。求不同的剖分方案總數(shù)H(n)。H(n)即為Catalan數(shù)。例如，n=5時H(5)=5。分析Catalan數(shù)問題有著明顯的遞歸子問題特征。在計算Catalan數(shù)時雖然可以推導(dǎo)出只關(guān)于n的一般公式，但在推導(dǎo)過程中卻要用到遞歸公式。下面討論三種不同的解法，其中第三種解法沒有使用遞歸，它是由前兩種解法推導(dǎo)而出的。解法1對于多邊形V1V2Vn，對角線V1Vi（i=3,

10、4,n-1）將其分為兩部分，一部分是i邊形，另一部分是n-i+1邊形。因此，以對角線V1Vi為一個剖分方案的剖分方案數(shù)為H(i)*H(n-i+1)。還有一種的特殊情形，是對角線V2Vn將其分為一個三角形V1V2Vn和一個n-2+1邊形。為了讓它同樣符合粗體字給出的公式，規(guī)定H(2)=1。于是得到公式：H(n)=H(i)*H(n-i+1) （i=2,3,n-1） -公式(1)H(2)=1有了這個遞歸關(guān)系式，就可以用遞推法或遞歸法解出H(n)。解法2從V1向除了V2和Vn外的n-3個頂點可作n-3條對角線。每一條對角線V1Vi把多邊形剖分成兩部分，剖分方案數(shù)為H(i)*H(n-i+2)，由于Vi可

11、以是V3V4Vn-1中的任一點，且V1可換成V2，V3，Vn中任一點也有同樣的結(jié)果?？紤]到同一條對角線在2個頂點被重復(fù)計算了一次，于是對每個由頂點和對角線確定的剖分方案都乘以1/2，故有H(n)=n(1/2)H(i)*H(n-i+2) （i=3,4,n-1）把(1/2)提到外面，H(n)=n/(2*(n-3)H(i)*H(n-i+2) （i=3,4,n-1） -公式(2)規(guī)定H(2)=H(3)=1，這是合理的。由公式(2)和H(2)=1，同樣可以用遞推法或遞歸法解出H(n)。解法3 把公式(1)中的自變量改為n+1，再將剛剛得出的公式(2)代入公式(1)，得到H(n+1)=H(i)*H(n-i

12、+2) （i=2,3,n） 由公式(1)H(n+1)=2*H(n)+H(i)*H(n-i+2) （i=3,4,n-1） 由H(2)=1H(n+1)=(4n-6)/n*H(n) 由公式(2)H(n)=(4n-10)/(n-1)*H(n-1) -公式(3)這是一個較之前兩種解法更為簡單的遞歸公式，還可以繼續(xù)簡化為H(n)=1/(n-1)*C(n-2,2n-4) -公式(4)這就不需要再使用遞歸算法了。然而在程序設(shè)計上，公式(4)反而顯得更加復(fù)雜，因為要計算階乘。因此最后給出由公式(3)作為理論依據(jù)范例程序代碼。代碼相當(dāng)簡單，這都歸功于剛才的推導(dǎo)。如果用前兩種解法中的遞歸關(guān)系，程序會變得復(fù)雜且容易寫

13、錯。因此，有時對具體問題將遞歸關(guān)系公式進行必要的化簡也是至關(guān)重要的。代碼/ex4.cpp#include <iostream.h>#define MAXN 100long f(int x) if (x=3) return(1); else return(4*x-10)*f(x-1)/(x-1);main() int n; cout<<"nPlease input N for a Catalan number:" cin>>n; if ( (n<=MAXN) && (n>=3) ) cout<<&qu

14、ot;The answer is:"<<f(n);本例編程時還有一個細節(jié)問題需要注意。注意函數(shù)f中的斜體部分，按照公式(4)計算時一定要先進行乘法再進行除法運算，因為(4*x-10)并不總能整除(x-1)，如果先進行除法則除出的小數(shù)部分將自動被舍去，從而導(dǎo)致得到不正確的解。數(shù)學(xué)上許多有重要意義的計數(shù)問題都可以歸結(jié)為對Catalan數(shù)的研究?？梢钥吹剑纠械倪f歸關(guān)系經(jīng)簡化還是相當(dāng)簡單的。下面討論一個遞歸關(guān)系略為復(fù)雜的例子。例5快速排序問題?？焖倥判蚴浅绦蛟O(shè)計中經(jīng)常涉及的一種排序算法。它的最好時間復(fù)雜度為O(nlog2n)，最差為O(n2)，是一種不穩(wěn)定的排序方法（大小相同

15、的數(shù)在排序后可能交換位置）。算法描述快速排序的一種基本思想是：要將n個數(shù)按由小到大排列，在待排序的n個數(shù)中選取任一個數(shù)（在本例中取第一個），稱為基準(zhǔn)數(shù)，在每一次快速排序過程中設(shè)置兩個指示器i和j，對基準(zhǔn)數(shù)左邊和右邊的數(shù)同時從最左（i）和最右（j）開始進行掃描（i逐1遞增，j逐1遞減），直到找到從左邊開始的某個i大于或等于基準(zhǔn)數(shù)，從右邊開始的某個j小于或等于基準(zhǔn)數(shù)。一旦發(fā)現(xiàn)這樣的i和j（暫且稱之為一個“逆序?qū)Α保?，則把第i個數(shù)和第j個數(shù)交換位置，這樣它們就不再是逆序?qū)α?，緊接著再將i遞增1，j遞減1。如此反復(fù)，在交換過有限個逆序?qū)?，i和j將越來越靠近，最后“相遇”，即i和j指向同一個數(shù)，暫且稱

16、之為相遇數(shù)（極端情況下，如果一開始就不存在逆序?qū)?，i和j將直接“相遇”）。相遇后就保證數(shù)列中沒有逆序?qū)α耍ǔ嗽谏鲜龅臉O端情況下基準(zhǔn)數(shù)和自身也算構(gòu)成一個逆序?qū)?，注意粗體字給出的逆序?qū)Φ亩x）。繼續(xù)掃描，非極端情況下，由于數(shù)列中已經(jīng)沒有逆序?qū)?，i遞增1（如果相遇數(shù)小于基準(zhǔn)數(shù)）或者j遞減1（如果相遇數(shù)大于基準(zhǔn)數(shù)）后即算完成了一趟快速排序，這時第1到第j個數(shù)中的每個都保證小于或等于基準(zhǔn)數(shù)，第i到第n個數(shù)中的每個保證大于或等于基準(zhǔn)數(shù)。此時，遞歸調(diào)用函數(shù)，對第1到第j個數(shù)和第i到第n個數(shù)分別再進行一趟快速排序。如果在極端情況下，程序認為基準(zhǔn)數(shù)和自身構(gòu)成逆序?qū)?，則將基準(zhǔn)數(shù)與自身交換（這其實沒有作用）之后i

17、遞增1，j遞減1（注意斜體字給出的對逆序?qū)Φ奶幚矸椒ǎ?，同樣對?到第j個數(shù)和第i到第n個數(shù)分別再進行一趟快速排序。最后的問題就是確定遞歸邊界。由于被排序的數(shù)列將不斷被劃分為兩個至少含一個數(shù)的子列（因為在每趟排序最后進行遞歸調(diào)用函數(shù)時i<>j），最后子列的長度將變?yōu)?。這就是遞歸的邊界。在程序?qū)崿F(xiàn)是，本著“能排則排”的原則，只要第一個數(shù)小于j（或者第i個數(shù)小于最后一個數(shù)），即進行遞歸。主程序（遞歸函數(shù)體）void QuickSort(RecType R ,int s,int t) int i=s,j=t,k; RecType temp; if (s<t) temp=Rs /

18、用區(qū)間第1個記錄作為基準(zhǔn) while( i!=j) /從兩端向中間交替掃描，直至i=j; while( j>i&&Rj.key>temp.key) j-; if(i<j) Ri=Rj; i+; while( i<j&&Ri.key<temp.key) i+; if(i<j) Rj=Ri; j-; Ri=temp; QuickSort(R,s,i-1); QuickSort(R,i+1,t); 例6“九宮陣”智力游戲。問題描述一個9×9方陣，由9個“九宮格”組成，每個九宮格又由3×3共9個小格子組成。請在每個

19、空白小格子里面填上19的數(shù)字，使每個數(shù)字在每個九宮格內(nèi)以及在整個九宮陣中的每行、每列上均出現(xiàn)一次。（1）編程將下面圖中的九宮陣補充完整。（2）討論是否可能給出“九宮陣”的全部解？分析本題可利用回溯法解決，其基本思想為深度優(yōu)先搜索（DFS），這也是一種以分治策略為基礎(chǔ)的算法?；厮莘ㄅc純粹的DFS不同的是，它在搜索過程中不斷殺死不合題意的結(jié)點。這一點保證了解法的效率。首先考慮如何得出全部解的情況。解空間樹容易構(gòu)造，只需按順序（從第一行第一個數(shù)字開始到第一行最后一個，然后第二行，一直到最后一行最后一個數(shù)字）“嘗試”填入數(shù)字即可。為了解決這個問題，我們需要先編寫一個函數(shù)check，其原型為int ch

20、eck(int i,int j,int k)，用于求第i行第j列能否填上數(shù)字k。如果可以，返回1，否則返回0。由于我們是按順序填入數(shù)字的，看起來一個數(shù)字后面的數(shù)字并不在判斷能否填的范圍內(nèi)。但為了解決題中某個特解問題的方便，還是引入較為嚴(yán)謹?shù)呐袛喾椒?。函?shù)check代碼如下：int check(int i,int j,int k) int l,m,pi,pj; /1. Check the line for (l=1;l<=9;l+) if ( (l!=j) && (ail!=0) && (ail=k) ) return(0); /2. Check the c

21、olumn for (l=1;l<=9;l+) if ( (l!=i) && (alj!=0) && (alj=k) ) return(0); /3. Check the 3x3 matrix /3.1 Firstly we will have to check the parent_i(pi) and parent_j(pj) if (i<=3) pi=1; else if (i<=6) pi=4; else pi=7; if (j<=3) pj=1; else if (j<=6) pj=4; else pj=7; /3.2 No

22、w we can check it for (l=0;l<=2;l+) for (m=0;m<=2;m+) if ( (pi+l)!=i) && (pj+m)!=j) ) if ( ( api+lpj+m!=0 ) && ( api+lpj+m=k ) ) return(0); return(1);結(jié)合注釋很容易就能接受函數(shù)的思想，不予過多說明。下面考慮程序最重要的部分，即遞歸函數(shù)。思路是這樣的：假設(shè)某一格能填入某數(shù)，把這個格子看成解空間樹的一個結(jié)點，由它可以擴展出9個兒子，即下一格填什么數(shù)（由1到9逐個嘗試）。對下一格，同樣這樣考慮。不斷用函數(shù)ch

23、eck函數(shù)考察某一個能否填入某數(shù)，一旦函數(shù)check返回0，則殺死這個結(jié)點。如果能一直填到最后一個數(shù)，結(jié)點仍未被殺死，則這是一個解。這種思想可用偽代碼表示如下：procedure backtrack(i,j,k:integer); if check(i,j,k)=true then begin ai,j=k; Generate_next_i_and_j; if i<10 then begin for l:=1 to 9 do backtrack(i,j,l);endelse Do_Output;ai,j:=0; end;注意斜體的“ai,j:=0”必不可少！當(dāng)對某個結(jié)點(x,y)擴展的過

24、程中，可能在擴展到(x+m,y+n)時它的子樹被完全殺死（每個結(jié)點都被殺死，亦即按照(x,y)及之前的填數(shù)方案填數(shù)，無解）。這時需要保證(x,y)以后所填的數(shù)被重新置零，這個語句的作用即在每個結(jié)點被殺死時都將其置零。將偽代碼翻譯為C+代碼：backtrack(int i,int j,int k) int l; if (check(i,j,k)=1) aij=k; /Fill in the okay solution /Generate next i,j if (j<9) j+; else i+; j=1; /End of Generate next i,j if (i<10) fo

25、r (l=1;l<=9;l+) backtrack(i,j,l); else output(); aij=0; /*When fails and goes upperwards, the value must be cleared*/ 函數(shù)output()用雙重循環(huán)完成輸出。在主函數(shù)main()對backtrack(1,1,i)進行一個循環(huán)，i從1取到9，即可完成整個程序。運行時發(fā)現(xiàn)九宮格的解相當(dāng)多，即使保存到文件中也不現(xiàn)實。這就回答了第2個問題。對于第1個問題，將這個程序略加改動，即賦予全局數(shù)組a以初值，并在過程backtrack中產(chǎn)生下一個i和j時跳過有初值的部分，即可將程序轉(zhuǎn)化為求

26、填有部分空缺的九宮格程序。最后給出填充有部分空缺的九宮格的完整源代碼。#include <iostream>using namespace std;int a1111=0;int check(int i,int j,int k) int l,m,pi,pj; /1. Check the line for (l=1;l<=9;l+) if ( (l!=j) && (ail!=0) && (ail=k) ) return(0); /2. Check the column for (l=1;l<=9;l+) if ( (l!=i) &&

27、amp; (alj!=0) && (alj=k) ) return(0); /3. Check the 3x3 matrix /3.1 Firstly we will have to check the parent_i(pi) and parent_j(pj) if (i<=3) pi=1; else if (i<=6) pi=4; else pi=7; if (j<=3) pj=1; else if (j<=6) pj=4; else pj=7; /3.2 Now we can check it for (l=0;l<=2;l+) for (m=0;m<=2;m+) if ( (pi+l)!=i) && (pj+m)!=j) ) if ( ( api+lpj+m!=0 ) && ( api+lpj+m=k ) ) return(0); return(1); void output() int i,j;