遞歸演算法

㈠ 什麼是遞歸演算法

遞歸做為一種演算法在程序設計語言中廣泛應用.是指函數/過程/子程序在運行過程序中直接或間接調用自身而產生的重入現像.

程序調用自身的編程技巧稱為遞歸（ recursion）。
一個過程或函數在其定義或說明中又直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。用遞歸思想寫出的程序往往十分簡潔易懂。
一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
注意：
(1) 遞歸就是在過程或函數里調用自身;
(2) 在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口，否則將無限進行下去（死鎖）。

遞歸演算法一般用於解決三類問題：
(1)數據的定義是按遞歸定義的。(Fibonacci函數)
(2)問題解法按遞歸演算法實現。(回溯)
(3)數據的結構形式是按遞歸定義的。(樹的遍歷，圖的搜索)

遞歸的缺點：
遞歸演算法解題的運行效率較低。在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。

㈡ 什麼是遞歸演算法有什麼作用

作者名：不詳 來源：網友提供 05年7月7日

無法貼圖 ，自己到 http://51zk.csai.cn/sjjg/NO00223.htm 看去吧

1、調用子程序的含義：
在過程和函數的學習中，我們知道調用子程序的一般形式是：主程序調用子程序A，子程序A調用子程序B，如圖如示，這個過程實際上是：

＠當主程序執行到調用子程序A語句時，系統保存一些必要的現場數據，然後執行類似於BASIC語言的GOTO語句，跳轉到子程序A（為了說得簡單些，我這里忽略了參數傳遞這個過程）。
＠當子程序A執行到調用子程序B語句時，系統作法如上，跳轉到子程序B。
＠子程序B執行完所有語句後，跳轉回子程序A調用子程序B語句的下一條語句（我這又忽略了返回值處理）
＠子程序A執行完後，跳轉回主程序調用子程序A語句的下一條語句
＠主程序執行到結束。
做個比較：我在吃飯（執行主程序）吃到一半時，某人叫我（執行子程序A），話正說到一半，電話又響了起來（執行子程序B），我只要先接完電話，再和某人把話說完，最後把飯吃完（我這飯吃得也夠累的了J）。
2、認識遞歸函數
我們在高中時都學過數學歸納法，例：
求 n！
我們可以把n！這么定義

也就是說要求3！，我們必須先求出2！，要求2！，必須先求1！，要求1！，就必須先求0！，而0!=1，所以1!=0!*1=1，再進而求2!，3!。分別用函數表示，則如圖：

我們可以觀察到，除計算0！子程序外，其他的子程序基本相似，我們可以設計這么一個子程序：
int factorial(int i){
int res;
res=factorial(I-1)*i;
return res;
}
那麼當執行主程序語句s=factorial(3)時，就會執行factorial(3),但在執行factorial(3)，又會調用factorial(2)，這時大家要注意，factorial(3)和factorial(2)雖然是同一個代碼段，但在內存中它的數據區是兩份！而執行factorial(2)時又會調用factorial（1），執行factorial（1）時又會調用factorial（0），每調用一次factorial函數，它就會在內存中新增一個數據區，那麼這些復制了多份的函數大家可以把它看成是多個不同名的函數來理解；
但我們這個函數有點問題，在執行factorial（0）時，它又會調用factorial（－1）。。。造成死循環，也就是說，在factorial函數中，我們要在適當的時候保證不再調用該函數，也就是不執行res=factorial(I-1)*i;這條調用語句。所以函數要改成：
int factorial(int i){
int res;
if (I>0) res=factorial(I-1)*i; else res=1;
return res;
}
那麼求3!的實際執行過程如圖所示：

3、如何考慮用遞歸的方法來解決問題
例：求s=1+2+3+4+5+6+……+n
本來這個問題我們過去常用循環累加的方法。而這里如要用遞歸的方法，必須考慮兩點：
1） 能否把問題轉化成遞歸形式的描述；
2） 是否有遞歸結束的邊界條件。
設:函數s(n)=1+2+3+…+(n-1)+n
顯然遞歸的兩個條件都有了：
1） s(n) =s(n-1)+n
2） s(1)=1
所以源程序為：
int progression(int n){
int res;
if (n=1 )res=1 else res=progression(n-1)+n;
return res;
}
4、遞歸的應用
中序遍歷二叉樹
void inorder (BinTree T){
if (T){
inorder(T->lchild);
printf(「%c」,T->data);
inorder(T->rchild);
}
}
現假設樹如圖（為了講解方便，樹很簡單）

＠執行第一次調用inorder1，T指向頂結點，T不為空，所以第二次調用inorder2；
＠T指向頂結點的左子樹結點也就是B，不為空，所以第三次調用inorder3；
＠T指向B結點的左子樹結點，為空，所以什麼都不執行，返回inorder2；
＠列印B結點的DATA域值「b」；
＠第四次調用inorder4，去訪問B子樹的右結點
＠T指向B結點的右子樹結點，為空，所以什麼都不執行，返回inorder2；
＠返回inorder1；
＠列印A結點的DATA域值「a」；
＠第五次調用inorder5，去訪問A子樹的右結點；
＠T指向A結點的右子樹結點，為空，所以什麼都不執行，返回inorder1；
＠inorder1執行完畢，返回。

㈢ 求階乘n!的遞歸演算法

#include<stdio.h>
int fun(int n)
{
if(n==1||n==0) return 1;//如果參數是0或者1返回1
return n*fun(n-1);//否則返回n和下次遞歸的積
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",fun(n));
return 0;
}
/*
5
120
*/

【遞歸演算法的原理】

遞歸是計算機科學的一個重要概念,遞歸的方法是程序設計中有效的方法,採用遞歸編寫
遞歸能使程序變得簡潔和清晰。

㈣ 遞歸演算法

0+1 =1
1+1 =2
1+2 =3
2+3 = 5
3+5 =8
.....
an = a(n-1)+a(n-2)
sn = a1+a2+....+an=......
時間有限後面的自己夠定吧

㈤ 快排 遞歸演算法

procere qsort(i,j:longint);
var r,l:longint;mid,temp:longint;
begin
r:=j;
l:=i;
mid:=a[r];
repeat
while a[r]>mid do dec(r);
while a[l]<mid do inc(l);
if r>=l
then
begin
temp:=a[r];
a[r]:=a[l];
a[l]:=temp;
inc(l);dec(r);
end;
until r<l;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
//A是排序數組
//基本方法:把小於MIN的放在一邊,
把大於MIN的放在另一邊. 遞歸解決.時間復雜度o(n*log(n))

㈥ C語言遞歸演算法

int f(int n)
{
if (n>0)
{
return n*f(n/2);
}
else if(n==0)
{
return n+1;
}
}

㈦ 遞歸演算法是什麼

遞歸演算法（英語：recursion algorithm）在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。

遞歸式方法可以被用於解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念。絕大多數編程語言支持函數的自調用，在這些語言中函數可以通過調用自身來進行遞歸。

計算理論可以證明遞歸的作用可以完全取代循環，因此在很多函數編程語言（如Scheme）中習慣用遞歸來實現循環。

㈧ 樹的遞歸演算法

答案是正確的啊。
if(root)就是如果root!=0，這里root是一個指針，指向結構體struct node的指針，第一次進入函數它就是指向根節點A的指針
運行步驟：
如果指向A的指針不為空(不為0),列印'A',
遞歸調用函數指向A的左孩子節點
如果指向B的指針不為空(不為0),列印'B',
遞歸調用函數指向B的左孩子節點
如果指向C的指針不為空(不為0),列印'C',
遞歸調用函數指向C的左孩子節點
由於C的左孩子節點為空，所以本次遞歸traversal(root->lchild)結束，回到上一層遞歸中即從C的左孩子節點回到C中，然後執行traversal(root->lchild)這一句下面一句，列印出'C'
然後遞歸調用traversal(root->rchild);指向C的右孩子節點
如果指向E的指針不為空(不為0),列印'E',
然後再遞歸指向E的左孩子節點，為空再返回到E中，再次列印出'E',然後再指向E的右孩子節點，為空，E的遞歸結束返回上一層遞歸即C中，然後C也到達末尾結束返回上一層遞歸B中，然後執行traversal(root->lchild)這一句下面一句，列印出'B'
然後遞歸調用traversal(root->rchild);指向B的右孩子節點
......
如此不斷進入某個節點的子節點操作後再從子節點返回父節點，層層進入再層層向上返回，從而遍歷樹中各個節點，最終得出結果：
A B C C E E B A D F F D G G

㈨ 什麼是遞歸演算法

遞歸演算法就是一個函數通過不斷對自己的調用而求得最終結果的一種思維巧妙但是開銷很大的演算法。
比如：
漢諾塔的遞歸演算法：
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個的情況。

㈩ 簡單的遞歸演算法

我不明白什麼是對對象依賴太大。這個全用static，不存在對象：）
public class DrawStar {
public static void main(String[] args) {
drawStar(5);
}

private static void drawStar(int n) {
if (n > 0) {
drawLine(n);
drawStar(n - 1);
drawLine(n);
}
}

private static void drawLine(int n) {
for (int i = 0; i < n; i++)
System.out.print("*");
System.out.println();
}
}