1、1 引言遞歸程序處理的問題可以分成兩類：第一類是數學上的遞歸函數，要求算得一個函數值，例如階乘函數和Fibonacci函數；第二類問題具有遞歸特征，目的可能是求出滿足某種條件的操作序列，例如Hanoi塔和八皇后問題。

2、第一類問題的程序設計是簡單的、機械的，而第二類問題則不然，由于涉及面廣，沒有統一的規則可循，所以編程過程往往比較復雜，而且編得的程序也不大好理解。

(相關資料圖)

3、究其原因在于，第一類問題已經有了現成的函數公式，第二類則沒有。

4、如果我們對于第二類問題也能寫出它的遞歸公式，那么編碼過程會大大簡化，而且還可以改善程序的可讀性。

5、本文將借助兩個程序實例討論這種方法。

6、2 公式化方法程序設計可以分成兩個階段：邏輯階段和實現階段。

7、邏輯階段要確定算法，不必考慮編程語言和實現環境。

8、通常算法可以用自然語言、流程圖、NS圖等工具來表示，對于第二類問題能在邏輯階段得出它的遞歸公式，那么至少有這樣幾個好處：1. 把邏輯階段同實現階段截然分開，大大簡化程序設計。

9、2. 用數學方法推導遞歸公式，要比用其他方法設計算法要簡單得多。

10、3. 由于公式是算法的最精確最簡潔的描述形式，有了遞歸公式，編碼工作就變得異常簡單，而且程序的可讀性也會很好。

11、所謂遞歸程序設計的公式化方法，首先要把問題表示成數學意義下的遞歸函數，那么關鍵是確定函數值的意義，盡管問題本身未必需要計算什么函數值。

12、函數值的選取可能不是唯一的，但是愈能表現問題本質愈好。

13、Hanoi塔問題要求顯示為把若干個盤子從一柱搬到另一柱要采取的動作，我們可以把動作的個數取為函數值。

14、于是得到有四個自變量的遞歸函數h(d，f，t，u)，其意義是以u柱（using）為緩沖把d個盤子（disks）從f柱（from）搬到t柱（to）。

15、容易得到下面的遞歸公式：h(1,f,t,u)=1h(d,f,t,u)= h(d-1,f,u,t)+ h(1,f,t,u)+ h(d-1,u,t,f), 如果d>1其實際意義非常明顯：搬動一個盤子只需一個動作；而把f柱上的d個盤子從f柱搬到t柱，需要先把上面的d-1個盤子從f柱搬到u柱，再把最下面的一個盤子從f柱搬到t柱，最后把已在u柱上的d-1盤子搬到t柱，因此總的動作個數等于三組動作之和。

16、有了遞歸公式，編程就變得極為簡單。

17、程序的結構是一個多分支結構，恰好同遞歸公式一一對應，編程幾乎變成了機械的翻譯。

18、在下面的程序中，遞歸函數與遞歸公式的差別只有當d為1時不僅要把動作個數v置為1，同時還要顯示此動作。

19、main(){ int d,v,h(int,int,int,int);printf("disks = ");scanf("%d",&d);v=h(d,1,2,3);printf("%d actions for %d disks!",v,d);}int h(int d,int f,int t,int u){ int i,v;if(d==1){v=1;printf("%d->%d ",f,t);}else v=h(d-1,f,u,t)+h(1,f,t,u)+h(d-1,u,t,f);return v;}此程序的運行會話如下：disks = 31->2 1->3 2->3 1->2 3->1 3->2 1->27 actions for 3 disks!3 例子：八皇后問題八皇后問題[2]是一個更有代表性更復雜的遞歸例題，要求在8×8的國際象棋棋盤上擺放8個皇后，使她們不致互相攻擊。

20、我們采取的算法仍然是從棋盤第一行開始每行放一個皇后，對于每一行都從該行的第一列開始放置，并判斷它同前面的那些皇后是否互相攻擊，如是就換成下一列，否則繼續放置下一個皇后，直至放好8個皇后。

21、依照這種思想，我們定義一個有9個自變量的函數:q（k,a1,a2,a3,a4,a5,a6,a7,a8）其中k表示已放置的皇后個數，而ai（此處i<=k）表示第i行上的皇后所在列的列號，因此這9個自變量能夠代表求解過程中任一時刻的狀態，而函數值定義為從此狀態出發能得到的解的個數。

22、按照這一思想不難得到下面的遞歸公式：q（k,a1,...,ak,0,...0）= 0 如果有0

23、將上面的遞歸公式很容易地翻譯成如下程序：main(){ int a[9],v,q(int,int *);v=q(0,a);printf("There are %d solutions!",v);}int q(int k,int *a){ int i,u,v;for(i=1,u=1;i

24、在q( )中首先計算ak是否同其前的所有ai相容，若是變量u非0。

25、q( )與遞歸公式嚴格對應，呈現出有三個選擇的分支結構。

26、在u非0且k為8的情況下，置函數值v為1，并顯示已得到的解。

27、顯然這個程序編寫起來最為簡單，而且最好理解。

28、下面給出該程序的交互會話，為節省版面只列出92個解中的4個：15863724 16837425 ... 83162574 84136275There are 92 solutions!4 結束語公式化方法是一種簡單而有效的設計思想，它把程序設計和程序理解的難點都集中到遞歸公式上。

29、從上面的例子可以看到這種思想能夠簡化程序設計，而且得到的程序顯然好于通常的程序。

30、這種思想有普遍性，至少適用多數遞歸程序的設計。

31、由遞歸公式設計出的程序具有標準的分支結構，編寫和理解都要簡單得多。

32、上面的兩個例題在求得函數值的同時，很容易地得到了要求的序列，但對于一般的問題未必總是這樣。

33、筆者曾給出一種伴隨序列法，可以用來得到某些問題（如顯示所有從m個數中取n個數的組合）要求的序列。

本文到此分享完畢，希望對大家有所幫助。

標簽：