遞歸演算法講解

1. 求漢諾塔遞歸全過程的演算法詳解圖，記得一定要是圖釋哦！！！

圖解是什麼意思呀。
這個演算法 那麼簡單沒必要搞得那麼復雜吧。
an = an-1 + 1;
你明白這個等式的意義嗎？
這個等式已經包含了遞歸演算法的全部含義。

an 表示 n個數的和，an-1 表示n-1個數的和 ，an = an-1 + 1;表示n個數的和可以通過n-1個數的和來求的。
上述說明哪些情況可以使用遞歸呢？
那就是：已知前一個步驟可以求得後一個步驟的結果的情況，並且前一個步驟和後一個步驟是有規律過度的。
比如漢諾塔問題：
移n個盤是已移n-1個盤為條件的，兩者的共同點是移盤。所以可以用f（n）表示移n個盤，f(n-1)表示移n-1個盤，那麼移n個盤和移n-1個盤有什麼關系呢？
這就需要預先分析問題才能得出具體的關系
在這個問題中，把n個盤從a移到c需要三個步驟來完成。
1.n-1個盤從a移到b
2 1個盤從a移到c
3 n-1個盤從b移到c
已知n-1個盤從a移到b是可行的，為什麼？
因為移1個盤是可行，那麼移2個盤也是可行，移 3個盤是已移2個盤為條件的，所以移3個盤也是可行的，所以移n個 盤是可行的。
所以根據已知條件可以解得：
設f(n, a, b,c) 表示 把n個盤從a移到c 藉助b --------------------------這里很關鍵，這是搞懂遞歸的關鍵關鍵。
那麼把n-1個盤從a移到b 藉助c 怎樣表示呢？
很明顯是：f(n-1, a, c,b)
那麼把1個盤從a移到c怎樣表示呢?
很明顯是：f(1, a, b,c)
那麼把n-1個盤從b移到c 藉助a 怎樣表示呢？
很明顯是：f(n-1, b, a,c)

所以f(n, a, b,c) = ( f(n-1, a,c,b) , f(1, a, b,c), f(n-1, b,a,c))
這和等差等比數列一個原理。
沒有什麼 特別的。

記住是問題有這樣遞推關系才可以使用這種方法。
如果要你計算1+2+8+22 的結果 你就不能使用遞歸。
因為該問題的後一步驟與前一步驟不具有規律性，所以已知前一個步驟並不能求的後一個步驟的值
1+2+3+4 ...+
這個問題就可以使用遞歸
原因你懂了吧。
至於爬樓梯問題，無限級分類 問題等一些遞歸問題，那不過時小菜一碟。
一句話：後一步驟依賴前一步驟並且二者聯系具有規律性，運用遞歸必然成功。

2. 漢諾塔 遞歸演算法的詳細解釋請教高手

為了實現 n個盤從 藉助c 從a 移動到 b
思路如下：
首先考慮極限當只有一個盤的時候 只要 盤直接從 a -> b即可
那麼當有2個盤的時候就只要先把1號盤從a -> c 然後 把2號盤 a->b 再 把 2好盤從 c - > b
那麼當有n個盤的時候你只要先把 n-1個 盤 藉助 b 移動到 c 然後將 n號盤從 a -> b
那麼這時候只要將 n-1想辦法從c移動到 b 藉助 a 那麼就可以先把 n-2個盤藉助b移動到a
然後 把n-1號盤從c-> b如此遞歸就是了！
#include <stdio.h>

void mov(int n,char a,char b)
{
printf("盤%d : 從 %c ---> %c\n",n,a,b);
}

void Hanoi(int n,char a,char b,char c)
{
if(n == 0) return ;
Hanoi(n-1,a,c,b);
mov(n,a,b);
Hanoi(n-1,c,b,a);

}
int main()
{
Hanoi(2,'a','b','c');
return 0;
}

3. 遞歸是什麼要詳細解釋

階乘, 斐波那契數列, 快速排序, 還有漢諾塔問題, 都是遞歸的比較經典的問題, 你要什麼例子呢? 你究竟是想學遞歸還是做什麼? 樓上幾位講得是不錯的, 唯一遺憾的是都不是用PASCAL語言編的.
下面試一下用PASCAL編一個漢諾塔的程序, 我手頭沒有書, 想到哪編到哪, 不一定太規范.
有A, B, C三個柱, 在A上N個盤子, 要移到C上去.
用中文建一個程序就是:
begin
移(N-1)個盤子(A到B, 以C為中介); {頂上的盤子}
移1個盤子(A到C); {最底的盤子}
移(N-1)個盤子(B到C, 以A為中介); {第一步移到B的盤子}
end.

對於移一個盤子, 我們只要簡單地列印一下就可:
procere MoveSingle(Origin, Dest: Char);
begin
Writeln(Origin, '==>', Dest);
end;

這一段不編子程序也可.

對於移動多個盤子, 按前面分析的, 可如此實現:
procere MoveMult(Origin, Dest, Medi: Char, n: Integer);
begin
MoveMult(Origin, Medi, Dest, n-1); {將頂上的盤子移走}
MoveSingle(Origin, Dest); {移最下的盤子}
MoveMult(Medi, Dest, Origin, n-1); {再移頂上的盤子}
end;

注意, 在MoveMult子程序中又調用了MoveMult自身, 這就是所謂的遞歸.

分析一下, 當有3個盤子時, 為: 先移2個(A==>B), 再移底部的(A==>C), 再把B上的2個移至C.
那麼移2個是如何實現的呢? 先移1個(Ori==>Med), 再移1個(Ori==>Dest), 再移一個(Med==>Dest).
移1個時演算法如何? 顯然又要調用移0個, 而移0個則調用移-1個, 這顯然有問題了. 程序一直會進行下去, 直到堆棧溢出為止, 程序死了.
解決的辦法是: 當個數為1時直接調用MoveSingle不再遞歸.
所以遞歸要有一個終止條件, 否則會無限進行下去. 修改後的遞歸演算法為:

procere MoveMult(Origin, Dest, Medi: Char, n: Integer);
begin
if n > 1 then {當盤子數大於1時遞歸}
begin
MoveMult(Origin, Medi, Dest, n-1); {將頂上的盤子移走}
MoveSingle(Origin, Dest); {移最下的盤子}
MoveMult(Medi, Dest, Origin, n-1); {再移頂上的盤子}
end else MoveSingle(Origin, Dest); {當盤子數不大於1時直接移動}
end;

無限遞歸是遞歸演算法中要注意的, 如果你設計多了, 自然知道什麼時候可能會出現無限遞歸.

完整程序為:
program Hanoi(input, output);
var
n: Integer;

procere MoveSingle(Origin, Dest: Char);
begin
Writeln(Origin, '==>', Dest);
end;

procere MoveMult(Origin, Dest, Medi: Char, n: Integer);
begin
if n > 1 then
begin
MoveMult(Origin, Medi, Dest, n-1);
MoveSingle(Origin, Dest);
MoveMult(Medi, Dest, Origin, n-1);
end else MoveSingle(Origin, Dest);
end;

begin
Writeln('Hanoi program');
Write('Input a number: ');
Readln(n);
MoveMult('A', 'C', 'B', n);
end.

沒經調試, 如果你要用的話, 自己測試一下.

4. 遞歸的通俗解釋是什麼

程序調用自身的編程技巧稱為遞歸（ recursion）。遞歸作為一種演算法在程序設計語言中廣泛應用。

一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。

遞歸的能力在於用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

遞歸的缺點：

遞歸演算法解題相對常用的演算法如普通循環等，運行效率較低。因此，應該盡量避免使用遞歸，除非沒有更好的演算法或者某種特定情況，遞歸更為適合的時候。在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。

以上內容參考：網路-遞歸

5. 什麼是遞歸演算法有什麼作用

作者名：不詳 來源：網友提供 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執行完畢，返回。

6. 關於遞歸演算法的題，哪位大俠給我解釋下………………

第一次調用方法先開始執行輸出n+A，等待遞歸調用完成以後，再輸出n+B，最後方法運行完畢。
在這里可以發現在遞歸調用的時候，沒有改變它自己的n值。所以在遞歸調用之前的n和調用遞歸之後的n值是相同的。如果你了解棧的話就很好理解了，先進後出。這了也就是輸出A越早的，輸出B就越晚。

7. 漢諾塔遞歸演算法求詳解 （研究了5天了，沒有理解，如果能教會我願支付寶付現金20元）

首先要知道漢諾塔的基本思路.
漢諾塔有3根柱子. 為什麼要有3根呢? 那是因為要直接使一個柱子上的碟片全部移動到另一根柱子是不行的,必須要通過第三根柱子來中轉一下.
這種中轉思路就是關鍵了.
具體來說,如果我們要把A柱子上的碟片移動到C柱子上,那麼首先我們可以通過"某種方式"將A柱子上除了最底下的碟片以外的所有碟片移動到B柱子上去,也就是拿B柱子當中轉. 然後下一步就可以直接把A柱子上最底層的那張碟片移動到C柱子上了. 最後,我們再以同樣的方式,將B柱子上剩下的那堆碟片以同樣的"某種方式"移動到C上. 總體來看,我們就完成了A->C的碟片移動操作.

那麼剩下的問題就是,這"某種方式"是什麼呢? 其實思考一下可以發現,在進行這"某種方式"的時候,除去A上最大的那個,其餘碟片都是我們需要操作的, 這個時候由於A是最大,其他的碟片對他來說移動都沒有限制的(都會比他小). 那麼我們就可以暫時忽視這個最大的碟片.

以上面的例子來說,我們要移動A柱子上除了底層之外的所有碟片到B柱上,就可以暫時忽略掉A上最大的那個碟片. 發現沒有, 這個時候我們的問題變成是: 將A上的所有碟片(因為已經忽視掉了最大的那個了)移動到B上,C可以作為轉接(因為上面沒有碟片).

這一步意味著我們把一個n個碟片的漢諾塔問題轉化成了n-1個碟片的漢諾塔問題,從而這裡面就包含了遞歸意義.

最後說回到你的程序. 函數hanoi(n,a,b,c)正是這樣一個意味: 列印將a柱子上的n個碟片以b為中轉移動到c上的操作步驟. 而可以看到,在執行這個函數的時候,如果n=1,那麼由於只有一個碟片,可以直接列印a->c, 如果n>1,則先用hanoi(n-1,a,c,b), 以c為中轉將a上的n-1個碟片先移動到b上,再列印a->c,即將a上剩下最大的那個碟片移動到c, 然後再調用hanoi(n-1,b,a,c), 以a為中轉將b上的碟片移動到c上.
按如此的遞歸邏輯下去就可以得到全部的操作過程了.

8. 全排列遞歸演算法

希望我的答復可以幫助你加深理解：

第一，perm函數中的條件for(int i=k;i<=m;i++)應更正為 for(int i=k;i<m;i++)

第二，你可以在核心步驟的前後列印有關變數的值，分析查看每一步的具體執行情況，這是編程調試的重要能力，要加強。
第三，以下是我提供的附件程序及運行結果（以1,2,3這個數組的全排列），可輔助分析：

1. 程序源碼=================================================
#include <stdio.h>
#include <stdlib.h>
int N,P=0;

void swap(int a[],int i,int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}

void perm(int a[],int k,int m,int pk,int pm)
{
int i;
/*k為中間變數，m初始化為參與排列元素的起始坐標和終止坐標
pk,pm分別表示參與排列元素的起始坐標和終止坐標，整個遞歸過程保持不變*/
if(k==m)
{
printf("----->perm %d :\n",P/N+1);/*列印提示*/
for(i=pk;i<pm;i++)
{
printf("%d ",a[i]);
P=P+1;
}
printf("\n\n");
}
else
{
for(i=k;i<m;i++)
{
printf("a %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
swap(a,k,i);
printf("b %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
perm(a,k+1,m,pk,pm);
printf("c %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
swap(a,k,i);
printf("d %d,%d,%d,%d,%d\n",i,k,a[0],a[1],a[2]);
}
}
}

int main()
{
/*調節以下N值及對應數組內容，可列印對應數組對應的全排列*/
N=3;
int t[]={1,2,3};
/*調節以上N值及對應數組內容，可列印對應數組對應的全排列*/

perm(t,0,N,0,N);
printf("----->Over!\n");/*列印提示*/
system("pause");
return 0;
}

2.列印結果 ============================================================

a 0,0,1,2,3
b 0,0,1,2,3
a 1,1,1,2,3
b 1,1,1,2,3
a 2,2,1,2,3
b 2,2,1,2,3
----->perm 1 :
1 2 3

c 2,2,1,2,3
d 2,2,1,2,3
c 1,1,1,2,3
d 1,1,1,2,3
a 2,1,1,2,3
b 2,1,1,3,2
a 2,2,1,3,2
b 2,2,1,3,2
----->perm 2 :
1 3 2

c 2,2,1,3,2
d 2,2,1,3,2
c 2,1,1,3,2
d 2,1,1,2,3
c 0,0,1,2,3
d 0,0,1,2,3
a 1,0,1,2,3
b 1,0,2,1,3
a 1,1,2,1,3
b 1,1,2,1,3
a 2,2,2,1,3
b 2,2,2,1,3
----->perm 3 :
2 1 3

c 2,2,2,1,3
d 2,2,2,1,3
c 1,1,2,1,3
d 1,1,2,1,3
a 2,1,2,1,3
b 2,1,2,3,1
a 2,2,2,3,1
b 2,2,2,3,1
----->perm 4 :
2 3 1

c 2,2,2,3,1
d 2,2,2,3,1
c 2,1,2,3,1
d 2,1,2,1,3
c 1,0,2,1,3
d 1,0,1,2,3
a 2,0,1,2,3
b 2,0,3,2,1
a 1,1,3,2,1
b 1,1,3,2,1
a 2,2,3,2,1
b 2,2,3,2,1
----->perm 5 :
3 2 1

c 2,2,3,2,1
d 2,2,3,2,1
c 1,1,3,2,1
d 1,1,3,2,1
a 2,1,3,2,1
b 2,1,3,1,2
a 2,2,3,1,2
b 2,2,3,1,2
----->perm 6 :
3 1 2

c 2,2,3,1,2
d 2,2,3,1,2
c 2,1,3,1,2
d 2,1,3,2,1
c 2,0,3,2,1
d 2,0,1,2,3
----->Over!
請按任意鍵繼續. . .

9. 漢諾塔分治遞歸演算法解釋！

hanoi中的參數：從A（源）通過B（中轉）移動到C（目的）
先把n-1個從A通過C移動到B：hanoi(n-1,A,C,B,time);
再把最後那個從A移到C：move(A,C);
然後把那n-1個從B通過A移到C：hanoi(n-1,B,A,C,time)
注意每一步的目的是什麼

10. 圖的廣度優先遍歷的遞歸演算法（附詳細解釋）

廣度優先遍歷不是用隊列的嗎、、、、深度優先遍歷才是用遞歸回溯啊