遞歸演算法的理解
『壹』 什麼是遞歸演算法
遞歸做為一種演算法在程序設計語言中廣泛應用.是指函數/過程/子程序在運行過程序中直接或間接調用自身而產生的重入現像.
程序調用自身的編程技巧稱為遞歸（ recursion）。
一個過程或函數在其定義或說明中又直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。用遞歸思想寫出的程序往往十分簡潔易懂。
一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
注意：
(1) 遞歸就是在過程或函數里調用自身;
(2) 在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口，否則將無限進行下去（死鎖）。
遞歸演算法一般用於解決三類問題：
(1)數據的定義是按遞歸定義的。(Fibonacci函數)
(2)問題解法按遞歸演算法實現。(回溯)
(3)數據的結構形式是按遞歸定義的。(樹的遍歷，圖的搜索)
遞歸的缺點：
遞歸演算法解題的運行效率較低。在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。
『貳』 遞歸的通俗解釋是什麼
程序調用自身的編程技巧稱為遞歸（ recursion）。遞歸作為一種演算法在程序設計語言中廣泛應用。
一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。
遞歸的能力在於用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
遞歸的缺點：
遞歸演算法解題相對常用的演算法如普通循環等，運行效率較低。因此，應該盡量避免使用遞歸，除非沒有更好的演算法或者某種特定情況，遞歸更為適合的時候。在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。
以上內容參考：網路-遞歸
『叄』 常見演算法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
『肆』 遞歸演算法怎麼理解
問題一：遞歸演算法還不是很理解!!高手教一教! 遞歸（recursion）是指把一個大的問題轉化為同樣形式但小一些的問題加以解決的方法。C語言允許一個函數調用它本身，這就是遞歸調用。即在調用一個函數的過程中又直接或間接地調用函數本身。不加控制的遞歸都是無終止的自身調用，程序中是絕對不應該出現這種情況的。為了防止無休止的遞歸，程序中應控制遞歸的次數，在某條件成立時進行遞歸，條件不成立不進行遞歸調用。並且在遞歸的調用過程中，不斷改變遞歸的條件，以使遞歸條件不再成立。
同一問題可能既可以用遞歸演算法解決，也可以用非遞歸演算法解決，遞歸往往演算法設計簡單，出奇制勝，而普通演算法（通常用循環解決）往往設計稍復雜。但執行效率遞歸演算法遜於循環演算法。遞歸反復調用自己，需要佔用較多內存和計算機時間。但有一些問題只有用遞歸方法才能解決，如著名的漢諾塔問題。
遞歸程序設計的關鍵就是考慮問題的兩種情況，一種是普遍情況即函數值等於把問題遞推一步後的本函數的調用，一種是極端或端點情況，此時函數值有確定的一個值而無須再調用本函數。遞歸的過程就是從普遍情況逐步過渡到端點情況的過程。
例子：
5個坐在一起論年齡，問第五個人多少歲？他說比第四個人大兩歲。問第四個人多少歲，他說比第三個人大兩歲。問第三個人多少歲，他說比第二個人大兩歲。問第二個人多少歲，他說比第一個人大兩歲。問第一個人多少歲，他說10歲。請問第五個人幾歲？
int age(int n)
{ int x;
if(n>1) x=age(n-1)+2;
else if(n==1) x=10;
return x;
}
void main( )
{ printf(%d,age(5));}
問題二：什麼是遞歸演算法 遞歸演算法就是一個函數通過不斷對自己的調用而求得最終結果滾咐的一種思維巧妙但是開銷很大的演算法。
比如：
漢諾塔的遞歸演算法：
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時......>>
問題三：怎麼更好地終極理解遞歸演算法 遞歸的基本思想是把規模大的問題轉化為規模小的相似的子問題來解決。在函數實現時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，所以就產生了函數調用它自身的情況。另外這個解決問題的函數必須有明顯的結束條件，這樣就不會產生無限遞歸的情況了。
需注意的是，規模大轉化為規模小是核心思想，但遞歸並非是只做這步轉化，而是把規模大的問題分解為規模小的子問題和可以在子問題解決的基礎上剩餘的可以自行解決的部分。而後者就是歸的精髓所在，是在實際解決問題的過程。
問題四：怎樣才能深刻理解遞歸和回溯？ 遞歸的精華就在於大問題的分解，要學會宏觀的去看問題，如果這個大問題可分解為若干個性質相同的規模更小的問題，那麼我們只要不斷地去做分解，當這些小問題分解到我們能夠輕易解決的時候，大問題也就能迎刃而解了。如果你能獨立寫完遞歸創建二叉樹，前序、中序、後序遞歸遍歷以及遞歸計算二叉樹的最大深度，遞歸就基本能掌握了。
回溯本人用得很少，僅限於八皇後問題，所以幫不上啥了。
問題五：二叉樹的遞歸演算法到底該怎麼理解 這不就是在二叉排序樹上的遞歸查找，看程序
tree& find(const T& d, tree& t){
if(t==NULL) return t;如果二叉樹為空則返回空，查找失敗
if(t->data==d) return t;否則，如果當前根結點關鍵碼為d，則查找成功，當前根結點為待查找結點
if(d>t->data) return find(d, t->right);如果比根的關鍵碼大就遞歸查找右子樹
return find(d, t->left);如果比根的關鍵碼小就遞歸查找左子樹
}
二叉樹的遞歸定義的含義就是非空二叉樹，除了根以外，左右子樹都是二叉樹（可以為空）
問題六：怎麼理解遞歸演算法?我看了代碼但還是不理解? 函數自己調用自己就是遞歸啊。
從前有座山，山裡有座廟，廟里有個老和尚給小和尚講故事。講的內容是：
從前有座山，山裡有座廟，廟里有個老和尚給小和尚講故事，講
從前有座山，山裡有座廟，廟里有個老和尚給小和尚講故事……
跟循環差不多。而且浪費棧空間，效率不高。能夠轉化為循環最好。
問題七：數據結構中的二叉樹中的遞歸怎麼理解？ 以中序遍歷為例，思想是：
若二叉樹為空，則空操作；否則
（1）中序遍歷左子樹
（中序遍歷左子樹時也是這三步）
（2）訪問根結點
（3）中序遍歷右子樹
（當然右子樹也是重復著三步）
示例代碼：
int InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf(%d\t,T->data);
InOrderTraverse(T->rchild);
}
return OK;
}
問題八：java遞歸演算法，怎麼理解？？？ n! = (n-1)*n！
簡單理解，就是目前的所有任務，等於前面所有的任務+現在的任務。
比如你求 1。。。100的加法總和
實際上是 1... 99 的加法總和 + 100 就是了。
這就是遞歸的來源。
你只需要計算你前一步的任務，然後加上自己，就OK了。
前一步，在再次調用前前一步......
問題九：新手一個，有什麼更好理解遞歸的方法嗎？（c++） 遞歸的話就是重復調用方法直到滿足條件為止就停止這個方法，就跟循環類似，不過循環使用的方法一邊比較簡單
問題十：遞歸的原理解釋 遞歸的底層實現其實是一個棧.棧的特點是後進先出,也就是最後進入棧的事件是最先被處理的.
遞歸就是這樣運作.比如計算階乘函數F(n)=n!=n*F(n-1)=....
寫成遞歸,我用java
public static long F(long num){
if(num
『伍』 什麼是遞歸演算法
遞歸演算法就是一個函數通過不斷對自己的調用而求得最終結果的一種思維巧妙但是開銷很大的演算法。
比如：
漢諾塔的遞歸演算法：
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塊藉助hannoi函數的功能從B由A搬回到C 這樣的三步實習了n塊由A經過B到C這樣一個功能，同樣你不用糾結於hanoi函數到底如何實現這個功能的，只要知道他有這么一個神奇的功能就行
最後：遞歸都有收尾的時候對吧，收尾就是當只有一塊的時候漢諾塔怎麼個玩法呢？很簡單吧，直接把那一塊有Amove到C我們就完成了，所以hanoni這個函數最後還要加上 if(n==1)move(one,three);（當只有一塊時，直接有Amove到C位置就行）這么一個條件就能實現hanoin函數n>=1時將n個塊由A經由B搬到C的完整功能了。
遞歸這個復雜的思想就是這樣簡單解決的，呵呵 不知道你看懂沒？純手打，希望能幫你理解遞歸
總結起來就是不要管遞歸的具體實現細節步驟，只要知道他的功能是什麼，然後利用他自己的功能通過調用他自己去解決自己的功能（好繞口啊，日）最後加上一個極限情況的條件即可，比如上面說的1個的情況。
『陸』 什麼是遞歸演算法
一、含義不同：
遞歸是重復調用函數自身實現循環。迭代是函數內某段代碼實現循環，循環代碼中參與運算的變數同時是保存結果的變數，當前保存的結果作為下一次循環計算的初始值。寬高棚
遞歸循環中，遇到滿足終止條件的情況時逐層返回來結束。迭代則使用計數器結束循環。當然很多情況都是多種循環混合採用，這要根據具體需求。
二、結構不同：
遞歸與迭代都是基於控制結構：迭代用重復結構，而遞歸用選擇結構。 遞歸與迭代都涉及重復：迭代顯式使用重復結構，而遞歸通過重復函數調用實現重復。
遞歸與迭代都涉及終止測試：迭代在循環條件失敗時終止，遞歸慎則在遇到基本情況時終止，使用計數器控制重復的迭代和遞歸都逐漸到達終止點：迭代一直修改計數器，直到計數器值使循環條件失敗；遞歸不念納斷產生最初問題的簡化副本，直到達到基本情況。
遞歸演算法一般用於解決三類問題：
(1)數據的定義是按遞歸定義的。（Fibonacci函數）
(2)問題解法按遞歸演算法實現。
這類問題雖則本身沒有明顯的遞歸結構，但用遞歸求解比迭代求解更簡單，如Hanoi問題。
(3)數據的結構形式是按遞歸定義的。
如二叉樹、廣義表等，由於結構本身固有的遞歸特性，則它們的操作可遞歸地描述。
以上內容參考：網路-遞歸
『柒』 JAVA如何理解遞歸
1、遞歸做為一種演算法在程序設計語言中廣泛使用，是指函數/過程/子程序在運行過程中直接或間接調用自身而產生的重入現象。
2、遞歸演算法一般用於解決三類問題：
1）數據的定義是按遞歸定義的。（Fibonacci（斐波那契）的函數）
2）問題解法按遞歸演算法實現。（回溯）
3）數據的結構形式是按遞歸定義的。（樹的遍歷，圖的搜索）
『捌』 遞歸演算法
遞歸演算法
遞歸演算法流程
遞歸過程一般通過函數或子過程來實現。遞歸演算法：在函數或子過程的內部，直接或者間接地調用自己的演算法。
遞歸演算法的特點
遞歸演算法是一種直接或者間接地調用自身的演算法。在計算機編寫程序中，遞歸演算法對解決一大類問題是十分有效的，它往往使演算法的描述簡潔而且易於理解。 遞歸演算法解決問題的特點： (1) 遞歸就是在過程或函數里調用自身。 (2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。 (3) 遞歸演算法解題通常顯得很簡潔，但遞歸演算法解題的運行效率較低。所以一般不提倡用遞歸演算法設計程序。 (4) 在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸演算法設計程序。
遞歸演算法要求
遞歸演算法所體現的「重復」一般有三個要求： 一是每次調用在規模上都有所縮小(通常是減半)； 二是相鄰兩次重復之間有緊密的聯系，前一次要為後一次做准備(通常前一次的輸出就作為後一次的輸入)； 三是在問題的規模極小時必須用直接給出解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的(以規模未達到直接解答的大小為條件)，無條件遞歸調用將會成為死循環而不能正常結束。
舉例
描述：把一個整數按n(2<=n<=20)進製表示出來，並保存在給定字元串中。比如121用二進製表示得到結果為：「1111001」。 參數說明：s: 保存轉換後得到的結果。 n: 待轉換的整數。 b: n進制（2<=n<=20） void numbconv(char *s, int n, int b) { int len; if(n == 0) { strcpy(s, ""); return; } /* figure out first n-1 digits */ numbconv(s, n/b, b); /* add last digit */ len = strlen(s); s[len] = ""[n%b]; s[len+1] = '\0'; } void main(void) { char s[20]; int i, base; FILE *fin, *fout; fin = fopen("palsquare.in", "r"); fout = fopen("palsquare.out", "w"); assert(fin != NULL && fout != NULL); fscanf(fin, "%d", &base); /*PLS set START and END*/ for(i=START; i <= END; i++) { numbconv(s, i*i, base); fprintf(fout, "%s\n", s); } exit(0); }
編輯本段遞歸演算法簡析（PASCAL語言）
遞歸是計算機科學的一個重要概念,遞歸的方法是程序設計中有效的方法,採用遞歸編寫 程序能是程序變得簡潔和清晰.
一 遞歸的概念
1.概念 一個過程(或函數)直接或間接調用自己本身,這種過程(或函數)叫遞歸過程(或函數). 如: procere a; begin . . . a; . . . end; 這種方式是直接調用. 又如: procere c(形參);forward; procere b; 局部說明 begin . . c(實參); . . end; procere c; 局部說明； begin . . b; . . end; 這種方式是間接調用. 例1計算n!可用遞歸公式如下: fac:=n*fac(n-1) {當n>0時} fac(n)={ fac:=1; { 當n=0時} 可編寫程序如下: program facn; var n:integer; function fac(n:integer):real; begin if n=0 then fac:=1 else fac:=n*fac(n-1); end; begin write('n=');readln(n); writeln(n,'!=',fac(n):0:0); end. 例2 樓梯有n階台階,上樓可以一步上1階,也可以一步上2階,編一程序計算共有多少種不同的走法. 設n階台階的走法數為f(n) 顯然有 n=1 f(n)={ f(n-1)+f(n-2) n>2 可編程序如下： program louti; var n:integer; function f(x:integer):integer; begin if x=1 then f:=1 else if x=2 then f:=2 else f:=f(x-1)+f(x-2); end; begin write('n=');read(n); writeln('f(',n,')=',f(n)) end.
二 如何設計遞歸演算法
1.確定遞歸公式 2.確定邊界(終了)條件
三 典型例題
例3 漢諾塔問題 如圖:已知有三根針分別用1,2,3表示,在一號針中從小放n個盤子,現要求把所有的盤子 從1針全部移到3針,移動規則是:使用2針作為過度針,每次只移動一塊盤子,且每根針上 不能出現大盤壓小盤.找出移動次數最小的方案. 程序如下: program hanoi; var n:integer; procere move(n,a,b,c:integer); begin if n=1 then writeln(a,'->',c) else begin move(n-1,a,c,b); writeln(a,'--->',c); move(n-1,b,a,c); end; end; begin write('Enter n='); read(n); move(n,1,2,3); end. 例4 快速排序 快速排序的思想是:先從數據序列中選一個元素,並將序列中所有比該元素小的元素都放到它的右邊或左邊,再對左右兩邊分別用同樣的方法處之直到每一個待處理的序列的長度為1, 處理結束. 程序如下: program kspv; const n=7; type arr=array[1..n] of integer; var a:arr; i:integer; procere quicksort(var b:arr; s,t:integer); var i,j,x,t1:integer; begin i:=s;j:=t;x:=b ; repeat while (b[j]>=x) and (j>i) do j:=j-1; if j>i then begin t1:=b; b:=b[j];b[j]:=t1;end; while (b<=x) and (i<j) do i:=i+1; if i<j then begin t1:=b[j];b[j]:=b;b:=t1; end until i=j; b:=x; i:=i+1;j:=j-1; if s<j then quicksort(b,s,j); if i<t then quicksort(b,i,t); end; begin write('input data:'); for i:=1 to n do read(a); writeln; quicksort(a,1,n); write('output data:'); for i:=1 to n do write(a:6); writeln; end.
編輯本段{遞歸的一般模式}
procere aaa(k:integer); begin if k=1 then (邊界條件及必要操作) else begin aaa(k-1); (重復的操作); end; end;
開放分類：
編程，計算機，演算法
引自：http://ke..com/view/1733593.htm