成對遞歸演算法

『壹』 請問遞歸演算法的時間復雜度如何計算呢

遞歸演算法的時間復雜度在演算法中，當一個演算法中包含遞歸調用時，其時間復雜度的分析會轉化為一個遞歸方程求解，常用以下四種方法：

1.代入法(Substitution Method)

代入法的基本步驟是先推測遞歸方程的顯式解，然後用數學歸納法來驗證該解是否合理。

2.遞歸程序設計是程序設計中常用的一種方法，它可以解決所有有遞歸屬性的問題，並且是行之有效的.

3.但對於遞歸程序運行的效率比較低，無論是時間還是空間都比非遞歸程序更費，若在程序中消除遞歸調用，則其運行時間可大為節省.

『貳』 常見演算法1——遞歸演算法

遞歸演算法就是通過自身不斷反復調用自身以解決問題，其中最經典的也就是漢諾達和斐波納契數列的問題了。
1.漢諾塔問題
在印度，有這么一個古老的傳說：在世界中心貝拿勒斯（在印度北部）的聖廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片，一次只移動一片，不管在哪根針上，小片必在大片上面。當所有的金片都從梵天穿好的那根針上移到另外一概針上時，世界就將在一聲霹靂中消滅，梵塔、廟宇和眾生都將同歸於盡。

分析：挪到C的金片也是從下到上由大到小的順序排列，那麼A之剩下最下面的金片移動到C的時候，C上面是不可以有金片的，這個時候A上面只有第n個金片，B上面有n-1個金片，C上面沒有金片，然後這個情況就和剛開始情況相同了，只不過A和B顛倒了位置而已。
（1）n-1個金片從A通過C移動到B，n-1個金片從A通過C移動到B也是不斷調用自身逐步縮小范圍。通過遞歸調用後，就完成了A上面僅剩下最大的金片，C上面沒有金片，B上面有n-1個金片。
（2）最大的那個金片從A移動到C
（3）調用自身重復剛開始的情況，只不過現在有金片的是B，即B通過A把金片移動到C。

2.斐波納契數列
2.1生兔子問題
古典問題：3個月起每個月都生一對兔子，小兔子長到第三個月後每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數為多少？下面先從小到大分析下這個情況
分析：假設將兔子分為小中大三種，兔子從出生後從第三個月開始每個月就會生出一對兔子，也就是一旦兔子變為大兔子那麼他就生了一對兔子
分析情況圖如下

很明顯這個是一個為斐波那契數列，即如果用f(n)表示第n個月的兔子的對數，那麼f(n)=f(n-1)+f(n-2)

2.2走台階問題
一個台階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少總跳法，並分析演算法的時間復雜度。
分析：假設我們現在還有最後一步要走，可能的情況有哪些？
（1）我們站在第9級上，一步1級後到達頂端；
（2）我們站在第8級上，一步2級後到達頂端；
所以，最後一步可以走1級或者2級，不外乎兩種情況。
再假設，已知從0級到9級的走法有M種，從0級到8級的走法有N種，那麼從0到10級的走法和M、N有什麼關系呢？從0到10級的走法一共是多少種呢？答案是M+N。
所以逐步遞歸，說白了，這還是個Fibnacci數列。即f(n)=f(n-1)+f(n-2)，事件復雜度是2^n

台階問題的變種:
一個台階總共有n級，如果一次可以跳1級，也可以跳2級.....也可以跳n級。求總共有多少總跳法

分析：用Fib(n)表示跳上n階台階的跳法數。如果按照定義，Fib(0)肯定需要為0，否則沒有意義。但是我們設定Fib(0) = 1；n = 0是特殊情況，通過下面的分析就會知道，強制令Fib(0) = 1很有好處。因為Fib(0)等於幾都不影響我們解題，但是會影響我們下面的分析理解。

當n = 1 時， 只有一種跳法，即1階跳：Fib(1) = 1;

當n = 2 時， 有兩種跳的方式，一階跳和二階跳：Fib(2) = 2;

到這里為止，和普通跳台階是一樣的。

當n = 3 時，有三種跳的方式，第一次跳出一階後，對應Fib(3-1)種跳法； 第一次跳出二階後，對應Fib(3-2)種跳法；第一次跳出三階後，只有這一種跳法。Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4;

當n = 4時，有四種方式：第一次跳出一階，對應Fib(4-1)種跳法；第一次跳出二階，對應Fib(4-2)種跳法；第一次跳出三階，對應Fib(4-3)種跳法；第一次跳出四階，只有這一種跳法。所以，Fib(4) = Fib(4-1) + Fib(4-2) + Fib(4-3) + 1 = Fib(4-1) + Fib(4-2) + Fib(4-3) + Fib(4-4) 種跳法。

當n = n 時，共有n種跳的方式，第一次跳出一階後，後面還有Fib(n-1)中跳法； 第一次跳出二階後，後面還有Fib(n-2)中跳法..........................第一次跳出n階後，後面還有 Fib(n-n)中跳法。Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n) = Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)。

通過上述分析，我們就得到了通項公式：

因此，有 Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)

兩式相減得：Fib(n)-Fib(n-1) = Fib(n-1) =====》 Fib(n) = 2*Fib(n-1) n >= 3

這就是我們需要的遞推公式：Fib(n) = 2*Fib(n-1) n >= 3

『叄』 遞歸的原理解釋

遞歸的原理解釋：
遞歸，是函數實現的一個很重要的環節，很多程序中都或多或少的使用了遞歸函數。遞歸的意思就是函數自己調用自己本身，或者在自己函數調用的下級函數中調用自己。
遞歸之所以能實現，是因為函數的每個執行過程都在棧中有自己的形參和局部變數的拷貝，這些拷貝和函數的其他執行過程毫不相干。這種機制是當代大多數程序設計語言實現子程序結構的基礎，是使得遞歸成為可能。假定某個調用函數調用了一個被調用函數，再假定被調用函數又反過來調用了調用函數。這第二個調用就被稱為調用函數的遞歸，因為它發生在調用函數的當前執行過程運行完畢之前。而且，因為這個原先的調用函數、現在的被調用函數在棧中較低的位置有它獨立的一組參數和自變數，原先的參數和變數將不受影響，所以遞歸能正常工作。程序遍歷執行這些函數的過程就被稱為遞歸下降。
程序員需保證遞歸函數不會隨意改變靜態變數和全局變數的值，以避免在遞歸下降過程中的上層函數出錯。程序員還必須確保有一個終止條件來結束遞歸下降過程，並且返回到頂層。

『肆』 《演算法導論》三種解遞歸式的方法

代入法可以用來確定一個遞歸式的上界或下界。這種方法很有效，但只能用於解的形式很容易猜的情形。

例如，我們需要確定下面遞歸式的上界：

該遞歸式與歸並排序相似，我們可以猜測其解為

代入法要求證明，恰當選擇常數 c>0，可有 T(n)≤cn lgn。首先假設此上界對所有正數 m<n 都成立，特別是對於 m=n/2，有 T(n/2)≤c(n/2)lg(n/2)。將其代入遞歸式，得到：

其中，只要 c≥1，最後一步都會成立。

並不存在通用的方法來猜測遞歸式的正確解，但總有一些試探法可以幫助做出好的猜測：

如果某個遞歸式與先前見過的類似，則可猜測該遞歸式有類似的解。如，遞歸式

看起來比較難解，因為右式 T 的自變數中加了 17，但我們可以猜測這個多出來的項對解的影響不大，因為當 n 很大時， 與 之間的差別並不大，兩者都將 n 分成均勻的兩半。

另一種方法是先證明遞歸式的較松的上下界，然後再縮小不確定性區間。例如，對遞歸式 ，因為遞歸式中有 n，而我們可以證明初始上界為 。然後，逐步降低其上界，提高其下界，直到達到正確的漸近確界 。

有時，我們或許能夠猜出遞歸式解的漸近界，但卻會在歸納證明時出現一些問題。通常，問題出在歸納假設不夠強，無法證明其准確的界，遇到這種情況時，可以去掉一個低階項來修改所猜測的界，以使證明順利進行。如下面的遞歸式：

可以猜測其解為 ，即要證明對適當選擇的 c，有 。有所猜測的界對遞歸式做替換，得到

由此無法得到 ，無論 c 的值如何。如果猜測一個更大的界，如 ，雖然這確實是上界，但事實上，所猜測的解 卻是正確的。為了證明這一點，要做一個更強的歸納假設。

從直覺上說，猜測 幾乎是正確的，只是差了一個常數 1，即一個低階項，然而，就因為差了一項，數學歸納法就無法證明出期望的結果。從所作的猜測中減去一個低階項，即 是個常數。現在有

只要 b≥ 1。這里，c 要選的足夠大，以便能處理邊界條件。

你可能會覺得從所作的猜測中減去一項有點兒與直覺不符。為什麼不是增加一項來解決問題呢？關鍵在於要理解我們是在用數學歸納法：通過對更小的值作更強的假設，就可以證明對某個給定值的更強的結論。

在運用漸近表示時很容易出錯。例如，對遞歸式 ，由假設 ，並證明

就是錯誤的，因為 c 是常數，因而錯誤地證明了 。錯誤在於沒有證明歸納假設的准確形式，即 。

有時，對一個陌生的遞歸式作一些簡單的代數變換，就會使之變成讀者較熟悉的形式。如下例子：

這個式子看上去比較難，但可以對它進行簡化，方法是改動變數。為了方便起見，不考慮數的截取整數問題，如將 化為整數。設 ，得

再設 ，得到新的遞歸式

這個式子看起來與 就非常像了，這個新的遞歸式的界是： 。將 帶回 ，有 。

有時候，畫出一個遞歸樹是一種得到好猜測的直接方法。在遞歸樹中，每一個節點都代表遞歸函數調用集合中一個子問題的代價。將樹中每一層內的代價相加得到一個每層代價的集合，再將每層的代價相加，得到的結果是所有層次的總代價。當用遞歸式表示分治演算法的運行時間時，遞歸樹的方法尤其有用。

遞歸樹最適合用來產生好的猜測，然後用代入法加以驗證。但使用遞歸樹產生好的猜測時，通常可以容忍小量的「不良量」，因為稍後就會證明所做的猜測。如果畫遞歸樹時非常地仔細，並且將代價都加了起來，那麼就可以直接用遞歸樹作為遞歸式的解的證明。

在講述例子之前，我們先來看一個幾何級數公式

對於實數 x≠1，式

是一個幾何級數（或稱指數級數），其值為

當和是無限的且 |x|<1 時，有無限遞減幾何級數

我們以遞歸式

為例來看一下如何用遞歸樹生成一個好的猜測。首先關注如何尋找解的一個上界，因為我們知道舍入對求解遞歸式通常沒有影響（此處即是我們需要忍受不精確的一個例子），因此可以為遞歸式

創建一顆遞歸樹，其中已將漸近符號改寫為隱含的常數系數 c>0。

構造的遞歸樹如下：

求所有層次的代價之和，確定整棵樹的代價：

最後的這個公式看起來不夠整潔，但我們可以再次充分利用一定程度的不精確，並利用無限遞減幾何級數作為上界。回退一步，得到：

此時，我們得到了遞歸式的一個猜測，在上面的例子里， 系數形成了一個遞減的等比級數，可知這些系數的總和的上界是常數 。由於樹根所需的代價為 ，所以根部的代價占總代價的一個常數部分。換句話說，整棵樹的總代價是由根部的代價所決定的。

事實上，如果 確實是此遞歸式的上界，那麼它一定是確界，為什麼呢？第一個遞歸調用所需要的代價是 ，所以 一定是此遞歸式的下界。

現在我們可以使用代換法來驗證猜測的正確性， 是遞歸式 的一個上界。只需要證明，當某常數 d>0， 成立。適用與前面相同的常數 c>0，有

只要 d≥ ，最後一步都會成立。

上圖是遞歸式

對應的遞歸樹。我們還是使用 c 來代表 項常數因子。當將遞歸樹內各層的數值加起來時，可以得到每一層的 cn 值。從根部到葉子的最長路徑是 。因為當 時， ，所以樹的深度是 。

直覺上，我們預期遞歸式的解至多是層數乘以每層的代價，也就是 。總代價被均勻地分布到遞歸樹內的每一層上。這里還有一個復雜點：我們還沒有考慮葉子的代價。如果這棵樹是高度為 的完整二叉樹，那麼有 個葉子節點。由於葉子代價是常數，因此所有葉子代價的總和為 ，或者說 。然而，這棵遞歸樹並不是完整的二叉樹，少於 個葉子，而且從樹根往下的過程中，越來越多的內部結點在消失。因此，並不是所有層次都剛好需要 cn 代價；越靠近底層，需要的代價越少。我們可以計算出准確的總代價，但記住我們只是想要找出一個猜測來使用到代入法中。讓我們容忍這些誤差，而來證明上界為 的猜測是正確的。

事實上，可以用代入法來證明 是遞歸式解的上界。下面證明 ，當 d 是一個合適的正值常數，則

上式成立的條件是 。因此，沒有必要去更准確地計算遞歸樹中的代價。

主方法給出了求解遞歸式的「食譜」方法，即將規模為 n 的問題劃分為 a 個子問題的演算法的運行時間，每個子問題規模為 ，a 和 b 是正常數。a 個子問題被分別遞歸地解決，時間各為 。劃分原問題和合並答案的代價由函數 描述。

從技術正確性角度來看，遞歸式實際上沒有得到很好的定義，因為 可能不是一個整數。但用 向上取整或向下取整來代替 a 項 並不影響遞歸式的漸近行為，因而，在寫分治演算法時略去向下取整和向上取整函數會帶給很大的方便。

其中我們將 n/b 解釋為 n 除以 b 的向下取整或向上取整。那麼 T(n) 有如下漸近界：

在使用主定理之前，我們需要花一點時間嘗試理解它的含義。對於三種情況的每一種，將函數 f(n) 與函數 進行比較。直覺上，兩個函數較大者決定了遞歸式的解。若函數 更大，如情況 1，則解為 T(n)= ( )。若函數 f(n) 更大，如情況 3，則解為 T(n)= (f(n))。若兩個函數大小相當，如情況 2，則乘上一個對數因子，解為 T(n)= ( )= ( )。

另外還有一些技術問題需要加以理解。在第一種情況下，不僅要有 小於 ，還必須是多項式地小於，也就是說， 必須漸近小於 ，要相差一個因子 ，其中 是大於 0 的常數。在第三種情況下，不是 大於 就夠了，而是要多項式意義上的大於，而且還要滿足「正則」條件 。

注意：三種情況並沒有覆蓋所有可能的 f(n)。當 f(n) 只是小於 但不是多項式地小於時，在第一種情況和第二種情況之間就存在一條「溝」。類似情況下，當 f(n) 大於 ，但不是多項式地大於時，第二種情況和第三種情況之間就會存在一條「溝」。如果 f(n) 落在任一條「溝」中，或是第三種情況種規則性條件不成立，則主方法就不能用於解遞歸式。

使用主方法很簡單，首先確定主定理的哪種情況成立，即可得到解。

例如：

對於這個遞歸式，我們有 a=9，b=3，f(n)=n，因此 = = 。由於 f(n) = ，其中 ， 因此可以應用於主定理的情況 1，從而得到解 T(n) = Θ( ) 。

現在考慮

其中，a = 1， b = 3/2， f(n) = 1，因此 = = = 1 。由於 f(n) = = Θ(1) ，因此可應用於情況2，從而得到解 T(n) = Θ( ) 。

對於遞歸式

我們有 a = 3，b = 4，f(n) = nlgn，因此 = =O( )。由於 當 n，其中 ，因此，如果可以證明正則條件成立，即應用於情況 3。當 n 足夠大時，對於 ， ，因此，由情況 3，遞歸式的解為 T(n)= ( )。

主方法不能用於如下遞歸式：

雖然這個遞歸式看起來有恰當的形式：a=2，b=2， ，以及 。你可能錯誤地認為應該應用情況 3，因為 漸近大於 。問題出現在它並不是多項式意義上的大於。對任意正常數 ，比值 都漸近小於 。因此，遞歸式落入了情況 2 和情況 3 之間的間隙。

證明分為兩部分。第一部分分析「主」遞歸式 ，並作了簡化假設 僅定義在 b>1 的整數冪上，即 ， ， ，…。這部分從直覺上說明該定理為什麼是正確的。第二部分說明如何將分析擴展至對所有的正整數 n 都成立，主要是應用數學技巧來解決向下取整函數和向上取整函數的處理問題。

取正合冪時的證明

對於遞歸式

此時的假設是 n 為 b>1 的正合冪，且 b 不必是整數。分析可分成三個引理說明，第一個引理是將解原遞歸式的問題歸約為對一個含和式的求值的問題。第二個引理決定含和式的界，第三個引理把前兩個合在一起，證明當 n 為 b 的正合冪時主定理成立。

引理一 ：設 a≥1，b>1 為常數，f(n) 為定義在 b 的正合冪上的非負函數。定義 如下：

其中 i 是正整數，則有

證明：如下圖。根節點代價為 f(n)，它有 a 個子女，每個代價是 。（為方便起見可將 a 視為整數，但這對數學推導沒什麼影響。）每個子女又各有 a 個子女，代價為 。這樣就有 個結點離根的距離為 2。一般地，距根為 j 的結點有 個，每一個的代價為 。每一個葉結點的代價為 ，每一個都距根 ，因為 。樹中共有 個葉結點。

可以將樹中各層上的代價加起來而得到方程 ，第 j 層上內部結點的代價為 ，故各層內部結點的總代價和為

在其所基於的分治演算法中，這個和值表示了將問題分解成為子問題並將子問題的解合並時所花的代價，所有葉子的代價（即解 個規模為 1 的子問題的代價）為 。

根據遞歸樹，主定理的三種情況對應於樹中總代價的三種情況：1、由所有葉子節點的代價決定；2、均勻分布在各層上；3、由根結點的代價決定。

引理二 ：設 a≥1，b≥1 為常數， 為定義在 b 的整數冪上的非負函數。函數 由下式定義

對 b 的整數冪，該函數可被漸近限界為：

證明：對情況 1，有 ，這隱含著 。用它對方程 做代換，得

對 O 標記內的式子限界，方法是提出不變項並作簡化，得到一個上升幾何級數：

因為 b 與 都是常數，最後的表達式可化簡為 。用此表達式對 作替換，得

情況 1 得以驗證。

為證情況 2，假設 ，有 。用此式對方程 作替換，得

對 記號中的式子做類似情況 1 中的限界，但所得並非是幾何級數，而是每項都是相同的:

用此方程對 中的和式做替換，有

則情況 2 得以驗證。情況 3 也可以用類似的方式證明。

引理三 ：設 a≥1，b>1 是常量， 是定義在 b 的整數冪上的非負函數。定義 T(n) 如下：

其中 i 是正整數。對於 b 的整數冪，T(n) 可有如下漸近界：

證明：用引理二給出的界來對引理一中的式 求值。對情況 1 有

對情況 2 有

對情況 3 有

『伍』 設計遞歸演算法生成n個元素的所有排列對象

#include<iostream>
#include<iterator>
#include<algorithm>
using namespace std;

template<class T>
void permutation(T list[], int k, int m)
{
if (k == m)
{
(list, list + m + 1, ostream_iterator<T>(cout, "")); //將當前list排序
cout << endl;
}
else{
for (int i = k; i <= m; i++)
{
swap(list[i], list[k]); //將下標為i的元素交換到k位置，類似從list[k:m]中剔除操作
permutation(list, k + 1, m);
swap(list[i], list[k]);
}
}
}

int main(int argc, char* argv[])
{
char arr[3] = { 'a', 'b', 'c' };
cout << "排序結果如下：" << endl;
permutation(arr, 0, 2);
return 0;

}

(5)成對遞歸演算法擴展閱讀

遞歸，在數學與計算機科學中，是指在函數的定義中使用函數自身的方法。也就是說，遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。

通俗來說，遞歸演算法的實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法來表示問題的解。

遞歸的基本原理

第一：每一級的函數調用都有自己的變數。

第二：每一次函數調用都會有一次返回。

第三：遞歸函數中，位於遞歸調用前的語句和各級被調用函數具有相同的執行順序。

第四：遞歸函數中，位於遞歸調用後的語句的執行順序和各個被調用函數的順序相反。

第五：雖然每一級遞歸都有自己的變數，但是函數代碼並不會得到復制。

『陸』 設計遞歸演算法生成n個元素的所有排列對象

#include<iostream>
#include<cmath>
using namespace std;

int count(int n)

//算n的階乘——因為n個數能組成n!個數
{

if(n<1)

{

cout<<"輸入也錯！";

exit(0);

}

else

if(n==1)

return 1;

else

return count(n-1)*n;
}

int pow10(int n)
//算出10的n次方
{

int a;

if(n==0)

return 1;

else

for(int i=1;i<=n;i++)

a=10*pow10(n-1);

return a;
}
int * comm(int n)

//組合n!個數（這里用遞歸算）
{

int *a=new int[count(n)];

if(count(n)==1)

a[0]=1;

else

{

int *b=new int[count(n-1)];

b=comm(n-1);

for(int i=0;i<count(n-1);i++)

for(int j=0;j<n;j++)

a[i*n+j]=(b/pow10(j)*10+n)*pow10(j)+b%pow10(j);

}

return a;
}
void main()
{

int n;

cout<<"請輸入n=";

cin>>n;

int *a=new int[count(n)];

a=comm(n);

cout<<"1-"<<n<<"自然數所有的排列組合為：\
";

for(int i=0;i<count(n);i++)

cout<<a<<" ";
}

=======================================
#define MAX 1000
#include<stdio.h>

void DispArrangement(int a[MAX], int n, int deepth)
{

int i, temp;

if(deepth == 1) {

for(i = 1; i <= n; i ++) {

printf("%d", a);

}

printf("\
");

} else {

for(i = 1; i <= deepth; i ++ ){

temp = a[n - deepth + 1];

a[n - deepth + 1] = a[n - deepth + i];

a[n - deepth + i] = temp;

DispArrangement(a, n, deepth - 1);

temp = a[n - deepth + 1];

a[n - deepth + 1] = a[n - deepth + i];

a[n - deepth + i] = temp;

}

}
}

int main(void)
{

int i, n, a[MAX];

scanf("%d", &n);

for(i = 1; i <= n; i ++ ) {

a = i;

}

DispArrangement(a, n, n);

return 0;
}

『柒』 請教高人 遞歸演算法編寫思路技巧

一個子程序（過程或函數）的定義中又直接或間接地調用該子程序本身，稱為遞歸。遞歸是一種非常有用的程序設計方法。用遞歸演算法編寫的程序結構清晰，具有很好的可讀性。遞歸演算法的基本思想是：把規模大的、較難解決的問題變成規模較小的、易解決的同一問題。規模較小的問題又變成規模更小的問題，並且小到一定程度可以直接得出它的解，從而得到原來問題的解。
利用遞歸演算法解題，首先要對問題的以下三個方面進行分析：
一、決定問題規模的參數。需要用遞歸演算法解決的問題，其規模通常都是比較大的，在問題中決定規模大小（或問題復雜程度）的量有哪些？把它們找出來。
二、問題的邊界條件及邊界值。在什麼情況下可以直接得出問題的解？這就是問題的邊界條件及邊界值。
三、解決問題的通式。把規模大的、較難解決的問題變成規模較小、易解決的同一問題，需要通過哪些步驟或等式來實現？這是解決遞歸問題的難點。把這些步驟或等式確定下來。
把以上三個方面分析好之後，就可以在子程序中定義遞歸調用。其一般格式為：
if 邊界條件 1 成立 then
賦予邊界值 1
【 elseif 邊界條件 2 成立 then
賦予邊界值 2
┇ 】
else
調用解決問題的通式
endif
例 1 ： 計算勒讓德多項式的值

x 、 n 由鍵盤輸入。
分析： 當 n ＝ 0 或 n ＝ 1 時，多項式的值都可以直接求出來，只是當 n ＞ 1 時，才使問題變得復雜，決定問題復雜程度的參數是 n 。根據題目提供的已知條件，我們也很容易發現，問題的邊界條件及邊界值有兩個，分別是：當 n ＝ 0 時 P n (x) ＝ 1 和當 n ＝ 1 時 P n (x) ＝ x 。解決問題的通式是：
P n (x) ＝ ((2n － 1)P n － 1 (x) － (n － 1)P n － 2 (x)) ／ n 。
接下來按照上面介紹的一般格式定義遞歸子程序。
function Pnx(n as integer)
if n ＝ 0 then
Pnx ＝ 1
elseif n ＝ 1 then
Pnx ＝ x
else
Pnx ＝ ((2*n － 1)*Pnx(n － 1) － (n － 1)*Pnx(n － 2)) ／ n
endif
end function
例 2 ： Hanoi 塔問題：傳說印度教的主神梵天創造世界時，在印度北部佛教聖地貝拿勒斯聖廟里，安放了一塊黃銅板，板上插著三根寶石針，在其中一根寶石針上，自下而上地放著由大到小的 64 個金盤。這就是所謂的梵塔（ Hanoi ），如圖。梵天要求僧侶們堅持不渝地按下面的規則把 64 個盤子移到另一根針上：

(1) 一次只能移一個盤子；
(2) 盤子只許在三根針上存放；
(3) 永遠不許大盤壓小盤。
梵天宣稱，當把他創造世界之時所安放的 64 個盤子全部移到另一根針上時，世界將在一聲霹靂聲中毀滅。那時，他的虔誠的信徒都可以升天。
要求設計一個程序輸出盤子的移動過程。
分析： 為了使問題更具有普遍性，設共有 n 個金盤，並且將金盤由小到大依次編號為 1 ， 2 ，…， n 。要把放在 s(source) 針上的 n 個金盤移到目的針 o(objective) 上，當只有一個金盤，即 n ＝ 1 時，問題是比較簡單的，只要將編號為 1 的金盤從 s 針上直接移至 o 針上即可。可定義過程 move(s,1,o) 來實現。只是當 n>1 時，才使問題變得復雜。決定問題規模的參數是金盤的個數 n ；問題的邊界條件及邊界值是：當 n ＝ 1 時， move(s,1,o) 。
當金盤不止一個時，可以把最上面的 n － 1 個金盤看作一個整體。這樣 n 個金盤就分成了兩個部分：上面 n － 1 個金盤和最下面的編號為 n 的金盤。移動金盤的問題就可以分成下面三個子問題（三個步驟）：
(1) 藉助 o 針，將 n － 1 個金盤（依照上述法則）從 s 針移至 i(indirect) 針上；
(2) 將編號為 n 的金盤直接從 s 針移至 o 針上；
(3) 藉助 s 針，將 i 針上的 n － 1 個金盤（依照上述法則）移至 o 針上。如圖

其中第二步只移動一個金盤，很容易解決。第一、第三步雖然不能直接解決，但我們已經把移動 n 個金盤的問題變成了移動 n － 1 個金盤的問題，問題的規模變小了。如果再把第一、第三步分別分成類似的三個子問題，移動 n － 1 個金盤的問題還可以變成移動 n － 2 個金盤的問題，同樣可變成移動 n － 3 ，…， 1 個金盤的問題，從而將整個問題加以解決。
這三個步驟就是解決問題的通式，可以以過程的形式把它們定義下來：
hanoi(n － 1,s,o,i)
move(s,n,o)
hanoi(n － 1,i,s,o)
參考程序如下：
declare sub hanoi(n,s,i,o)
declare sub move(s,n,o)
input "How many disks?",n
s ＝ 1
i ＝ 2
o ＝ 3
call hanoi(n,s,i,o)
end
sub hanoi(n,s,i,o)
rem 遞歸子程序
if n ＝ 1 then
call move(s,1,o)
else
call hanoi(n － 1,s,o,i)
call move(s,n,o)
call hanoi(n － 1,i,s,o)
endif
end sub
sub move(s,n,o)
print "move disk";n;
print "from";s;"to";o
end sub

『捌』 什麼是遞推法和遞歸法

問題一：什麼是遞推法和遞歸法?兩者在思想有何聯系 程序調用自身的編程技巧稱為遞歸。遞歸做為一種演算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。
遞推演算法是一種用若干步可重復的簡運算（規律）來描述復雜問題的方法。遞推是序列計算機中的一種常用演算法。它是按照一定的規律來計算序列中的每個項，通常是通過計算機前面的一些項來得出序列中的指定象的值。
迭代是重復反饋過程的活動，其目的通常是為了逼近所需目標或結果。每一次對過程的重復稱為一次「迭代」，而每一次迭代得到的結果會作為下一次迭代的初始值。

問題二：遞推和遞歸演算法有什麼區別 遞歸指自我調用的函數，自己調用自己；遞推指重復進行的過程，重復進行一個過程，

問題三：的遞推和遞歸方法的區別是什麼 遞歸就是自己調用自己吧！
遞推是從頭向後推吧！

問題四：遞推和遞歸演算法有什麼區別 遞歸就是自己調用自己吧！
遞推是從頭向後推吧！

問題五：遞推和遞歸的區別是什麼 1.遞歸：將問題規模為n的問題，降解成若干個規模為n-1的問題，依次降解，直到問題規模可求，求出低階規模彎中的解，代入高階問題中，直至求出規模為n的問題的解。
2.遞推：構造低階的規模(如規模為i，一般i=0)的問題，並求出解，推導出問題規模為i+1的問題以及解，依次推到規模為n的問題。
3.遞歸包括回溯和遞推兩個過程。
最好的例子是斐波那契數列: 1 1 2 3 5 8 13 21 ... ...
總結成公式就是F(n+1)=F(n)+F(n-1), F(0)=F(1)=1;
你可以用遞歸的方法寫這個函數:
int F(int n) {
if (n 問題六：遞推演算法和遞歸演算法有什麼區別 遞推就是從前往後推,遞歸還有個回溯的過程
舉個例子,數列:1,1,2,3,5,8,13,21,……
要求第100項,就得從前兩項開始推,直到第100項,是一個遞推的過程
f[0]=f[1]=1;
for(i=2;i 問題七：遞推法和遞歸法兩者在思想有何聯系 兩者是一樣的，沒有本質區別。

問題八：遞推演算法的遞推與遞歸的世槐比較 相對於遞歸演算法,遞推演算法免除了數據埋返山進出棧的過程，也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.比如階乘函數：f(n)=n*f(n-1)在f(3)的運算過程中,遞歸的數據流動過程如下:f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}而遞推如下:f(0)-->f(1)-->f(2)-->f(3)由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推.但是遞歸作為比較基礎的演算法,它的作用不能忽視.所以,在把握這兩種演算法的時候應該特別注意。 所謂順推法是從已知條件出發，逐步推算出要解決的問題的方法叫順推。如斐波拉契數列，設它的函數為f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。則我們通過順推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我們要求的解。 所謂逆推法從已知問題的結果出發，用迭代表達式逐步推算出問題的開始的條件，即順推法的逆過程，稱為逆推。

問題九：什麼是遞歸演算法 遞歸演算法就是一個函數通過不斷對自己的調用而求得最終結果的一種思維巧妙但是開銷很大的演算法。
比如：
漢諾塔的遞歸演算法：
void move(char x,char y){
printf(%c-->%c\n,x,y);
}
void hanoi(int n,char one,char two,char three){
/*將n個盤從one座藉助two座，移到three座*/
if(n==1) move(one,three);
else{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}
main(){
int n;
printf(input the number of diskes:);
scanf(%d,&n);
printf(The step to moving %3d diskes:\n,n);
hanoi(n,'A','B','C');
}
我說下遞歸的理解方法
首先：對於遞歸這一類函數，你不要糾結於他是干什麼的，只要知道他的一個模糊功能是什麼就行，等於把他想像成一個能實現某項功能的黑盒子，而不去管它的內部操作先，好，我們來看下漢諾塔是怎麼樣解決的
首先按我上面說的把遞歸函數想像成某個功能的黑盒子，void hanoi(int n,char one,char two,char three); 這個遞歸函數的功能是：能將n個由小到大放置的小長方形從one 位置，經過two位置 移動到three位置。那麼你的主程序要解決的問題是要將m個的漢諾塊由A藉助B移動到C，根據我們上面說的漢諾塔的功能，我相信傻子也知道在主函數中寫道：hanoi(m,A,B,C)就能實現將m個塊由A藉助B碼放到C，對吧？所以，mian函數裡面有hanoi(m,'A','C','B');這個調用。
接下來我們看看要實現hannoi的這個功能，hannoi函數應該幹些什麼？
在hannoi函數里有這么三行
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
同樣以黑盒子的思想看待他，要想把n個塊由A經過B搬到C去，是不是可以分為上面三步呢？
這三部是：第一步將除了最後最長的那一塊以外的n-1塊由one位置經由three搬到two 也就是從A由C搬到B 然後把最下面最長那一塊用move函數把他從A直接搬到C 完事後 第三步再次將剛剛的n-1塊藉助hanno處函數的功能從B由A搬回到C 這樣的三步實習了n塊由A經過B到C這樣一個功能，同樣你不用糾結於hanoi函數到底如何實現這個功能的，只要知道他有這么一個神奇的功能就行
最後：遞歸都有收尾的時候對吧，收尾就是當只有一塊的時候漢諾塔怎麼個玩法呢？很簡單吧，直接把那一塊有Amove到C我們就完成了，所以hanoni這個函數最後還要加上 if(n==1)move(one,three);（當只有一塊時，直接有Amove到C位置就行）這么一個條件就能實現hanoin函數n>=1時......>>

問題十：遞歸和遞推有什麼不一樣。用起來哪個快一些？？ 遞推就是遞推循環，遞推或者說循環比遞歸更容易理解和運用，但遞歸演算法在運行速度上更快，代碼也比較簡潔。遞歸演算法也有缺點，主要是空間消耗比較大。從數學上說，所有的遞歸演算法都可以用遞推（循環）演算法代替，但不是所有的循環演算法都可以被遞歸代替。