遞推是一種應用非常廣泛的常用演算法之一，與下一章的遞迴有著密切的聯絡。本章**遞推在求解數列、數陣以及計數等應用案例方面的應用。
在紛繁變幻的世界，所有事物都隨時間的流逝發生著微妙的變化。許多現象的變化是有規律可循的，這種規律往往呈現出前因後果的關係。某種現象的變化結果與緊靠它前面變化的乙個或一些結果緊密關聯。
遞推的思想正體現了這一變化規律。
所謂遞推，是在命題歸納時，可以由nk,…,n1的情形推得n的情形。乙個線性遞推可以形式地寫成
其中f(n)=0時遞推是齊次的，否則是非齊次的。遞推的一般解法要用到n次方程的求根。
遞推關係是一種高效的數學模型，是組合數學中的乙個重要解題方法，在組合計數中有著廣泛的應用。在概率方面利用遞推可以解決一類基本事件個數較大的概率問題。在對多項式的求解過程中，很多情況可以使用遞推演算法來實現。
在行列式方面，某些n階行列式只用初等變換難以解決，但如果採用遞推求解則顯得較為容易。
遞推關係不僅在各數學分支中發揮著重要的作用，由它所體現出來的遞推思想在各學科領域中更是顯示出其獨特的魅力。
遞推是利用問題本身所具有的一種遞推關係求解問題的一種方法。設要求問題規模為n的解，當n=1時，解或為已知，或能非常方便地得到解。能採用遞推法構造演算法的遞推性質，能從已求得的規模為1,2,…,i1的一系列解，構造出問題規模為i的解。
這樣，程式可從i=0或i=1出發，重複地由已知至i1規模的解，通過遞推，獲得規模為i的解，直至得到規模為n的解。
遞推演算法的基本思想是把乙個複雜的龐大的計算過程轉化為簡單過程的多次重複，該演算法充分利用了計算機的運算速度快和不知疲倦的特點，從頭開始一步步地推出問題最終的結果。使用遞推演算法程式設計，既可使程式簡練，又可節省計算時間。
對於乙個序列來說，如果已知它的通項公式，那麼要求出數列中某項之值或求數列的前n項之和是簡單的。但是，在許多情況下，要得到數列的通項公式是困難的，甚至無法得到。然而，乙個有規律的數列的相鄰位置上的資料項之間通常存在著一定的關係，可以借助已知的項，利用特定的關係逐項推算出它的後繼項的值，直到找到所需的那一項為止。
遞推演算法避開了求通項公項的麻煩，把乙個複雜的問題的求解，分解成連續的若干步簡單運算。
遞推演算法的首要問題是得到相鄰的資料項之間的關係，即遞推關係。它針對這樣一類問題：問題的解決可以分為若干步驟，每個步驟都產生乙個子解（部分結果），每個子解都是由前面若干子解生成。
不同的子解，其所相關的問題規模也隨子解不同而遞增。我們把這種由前面的子解得出後面的子解的規則稱為遞推關係。
我們在設計求解問題前，要通過細心的觀察，豐富的聯想，不斷嘗試推理，盡可能歸納總結其內在規律，然後再把這種規律性的東西抽象成遞推數學模型。
利用遞推求解實際問題，需要掌握遞推的具體描述及其實施步驟。
1．實施遞推的步驟
（1）確定遞推變數
應用遞推演算法解決問題，要根據問題的具體實際設定遞推變數。遞推變數可以是簡單變數，也可以是一維或多維陣列。
（2）建立遞推關係
遞推關係是指如何從變數的前一些值推出其下乙個值或從變數的後一些值推出其上乙個值的公式（或關係）。遞推關係是遞推的依據，是解決遞推問題的關鍵。有些問題，其遞推關係是明確的，大多數實際問題並沒有現成的明確的遞推關係，需根據問題的具體實際，細心的觀察，豐富的聯想，不斷嘗試推理，才能確定問題的遞推關係。
（3）確定初始（邊界）條件
對所確定的遞推變數，要根據問題最簡單情形的資料確定遞推變數的初始（邊界）值，這是遞推的基礎。
（4）對遞推過程進行控制
遞推過程不能無休止地重複執行下去。遞推過程在什麼時候結束，滿足什麼條件結束，這是編寫遞推演算法必須考慮的問題。
遞推過程的控制通常可分為兩種情形：一種是所需的遞推次數是確定的值，可以計算出來；另一種是所需的遞推次數無法確定。對於前一種情況，可以構建乙個固定次數的迴圈來實現對遞推過程的控制；對於後一種情況，需要進一步分析出用來結束遞推過程的條件。
2．遞推演算法框架描述
遞推通常由迴圈來實現，一般在迴圈外確定初始（邊界）條件，在設定的迴圈中實施遞推。
下面歸納常用的遞推模式並作簡要的框架描述。
首先，從遞推流向可分為順推與逆推。
（1）簡單順推算法
順推即從前往後推，從已求得的規模為1,2,…,i1的一系列解，推出問題規模為i的解，直至得到規模為n的解。
簡單順推算法框架描述：
f(1i1)=《初始值》確定初始值
for(k=i;k<=n;k++)
f(k)=《遞推關係式》根據遞推關係實施遞推
printf(f(n輸出n規模的解f(n)
（2）簡單逆推算法
逆推即從後往前推，從已求得的規模為n,n1,…,i+1的一系列解，推出問題規模為i的解，直至得到規模為1的解。
簡單逆推算法框架描述：
f(n—i+1)=《初始值》確定初始值
for(k=i;k>=1;k)
f(k)=《遞推關係式》根據遞推關係實施遞推
printf(f(1輸出解f(1)
簡單遞推問題設定一維陣列實現，較複雜的遞推問題需設定二維或二維以上陣列。例如當規模為i的解為規模為1,2,…,i1的解通過計算處理決定時，可設定二重迴圈處理這一較為複雜的遞推。
（3）二維陣列順推算法
設遞推的二維陣列為f(k,j)，1≤k≤n,1≤j≤m，由初始條件分別求得f(1,1),f(1,2),…,f(1,m)，需求f(n,m)，則據給定的遞推關係由初始條件依次順推得f(2,1),f(2,2),…, f(2,m)；f(3,1),f(3,2),…, f(3,m)；…，直至得到所要求的解f(n,m)。
二維陣列順推算法框架描述：
f(1,1m)=《初始值》賦初始值
for(k=2;k<=n;k++)
for(j=1;j<=m;j++)
f(k,j)=《遞推關係式》根據遞推關係實施遞推
printf(f(n,m輸出n規模的解f(n,m)
二維或二維以上陣列遞推常用於動態規劃設計的最優值求解過程。當遞推關係包含兩個或兩個以上關係式時，通常應用多關係分級遞推演算法求解。
（4）多關係分級遞推演算法
f(1i1)=《初始值》賦初始值
for(k=i;k<=n;k++)
printf(f(n輸出n規模的解f(n)
關於遞推的時間複雜度，如果在一重迴圈中可完成遞推，通常其相應的時間複雜度為o(n)。在實際應用中，由於遞推關係的不同，往往需要二重或更複雜的迴圈結構才能完成遞推，其相應的時間複雜度為o(n2)或更高。
本節**雙冪序列與雙冪積序列這兩個典型的遞推序列問題的求解。
設x,y為正整數，試計算集合
的元素由小到大排列的雙冪序列第n項與前n項之和。
（1）遞推演算法設計
集合由2的冪與3的冪組成，實際上給出的是兩個遞推關係。
顯然，第1項也是最小項為1（當x=y=0時）。
從第2項開始，為了實現從小到大排列，設定a,b兩個變數，a為2的冪，b為3的冪，顯然a≠b。
設定k迴圈（k=2,3,…,n，其中n為鍵盤輸入整數），在k迴圈外賦初值：a=2;b=3;s=1;在k迴圈中通過比較賦值：
當a當a>b時，由賦值f[k]=b確定為序列的第k項；然後b=b*3，即b按遞推規律乘3，為後一輪比較作準備。
遞推過程描述：
a=2;b=3為遞推變數a,b賦初值
for(k=2;k<=n;k++)
在這一演算法中，變數a,b是變化的，分別代表2的冪與3的冪。
上述遞推演算法的時間複雜度與空間複雜度均為o(n)。
（2）雙冪序列程式實現
// 雙冪序列求解
#include <>
void main()
s+=f[k];
}printf(" 數列的第%d項為: %.0f ",m,f[m]);
if(t==2對輸出項進行標註
printf("(2^%d) \n",p2);
第3章程序管理 第3講
作業系統 主講人 黃伯虎 上一講內容回顧 程序間的相互作用 基本概念 同步 互斥 臨界資源 臨界區帶來的問題 解決方案 鎖變數法 測試和設定指令 訊號量和p v操作 訊號量的物理含義 s 0 表示可用資源數目。s 0 表示沒有資源可用。s 0 其絕對值表示因為此訊號量而被阻塞的程序數。p ss為訊號...
第3講銷售管理
1資訊科技與商務管理系25 1企業資源規劃 erp 資訊科技與商務管理系25 2企業資源規劃 erp 主要內容銷售管理業務型別 資訊科技與商務管理系25 3企業資源規劃 erp 企業銷售管理的職能是在企業供需鏈中處於市場 客戶 與企業 製造 資訊科技與商務管理系25 5企業資源規劃 erp 銷售管理...
第3講 Abstract Factory抽象工廠模式
2005.11.15 李建忠 new的問題 常規的物件建立方法 new的問題 實現依賴，不能應對 具體例項化型別 的變化 解決思路 封裝變化點 變化，封裝 潛台詞 如果沒有變化，當然不需要額外的封裝！工廠模式的緣起 變化點在 物件建立 因此就封裝 物件建立 面向介面程式設計 依賴介面，而非依賴實現 ...