遞歸演算法思想

① 請教高人 遞歸演算法編寫思路技巧

一個子程序（過程或函數）的定義中又直接或間接地調用該子程序本身，稱為遞歸。遞歸是一種非常有用的程序設計方法。用遞歸演算法編寫的程序結構清晰，具有很好的可讀性。遞歸演算法的基本思想是：把規模大的、較難解決的問題變成規模較小的、易解決的同一問題。規模較小的問題又變成規模更小的問題，並且小到一定程度可以直接得出它的解，從而得到原來問題的解。
利用遞歸演算法解題，首先要對問題的以下三個方面進行分析：
一、決定問題規模的參數。需要用遞歸演算法解決的問題，其規模通常都是比較大的，在問題中決定規模大小（或問題復雜程度）的量有哪些？把它們找出來。
二、問題的邊界條件及邊界值。在什麼情況下可以直接得出問題的解？這就是問題的邊界條件及邊界值。
三、解決問題的通式。把規模大的、較難解決的問題變成規模較小、易解決的同一問題，需要通過哪些步驟或等式來實現？這是解決遞歸問題的難點。把這些步驟或等式確定下來。
把以上三個方面分析好之後，就可以在子程序中定義遞歸調用。其一般格式為：
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、遞推法：遞推演算法是一種根據遞推關系進行問題求解的方法。通過已知條件，利用特定的遞推關系可以得出中間推論，直至得到問題的最終結果。遞推演算法分為順推法和逆推法兩種。 

2、遞歸法：在計算機編程中，一個函數在定義或說明中直接或間接調用自身的編程技巧稱為遞歸。通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸做為一種演算法在程序設計語言中廣泛應用。 

3、兩者的聯系：在問題求解思想上，遞推是從已知條件出發，一步步的遞推出未知項，直到問題的解。從思想上講，遞歸也是遞推的一種，只不過它是對待解問題的遞推，直到把一個復雜的問題遞推為簡單的易解問題。然後再一步步的返回去，從而得到原問題的解。 

(2)遞歸演算法思想擴展閱讀

相對於遞歸演算法,遞推演算法免除了數據進出棧的過程，也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值。

比如階乘函數：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)   由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推。

但是遞歸作為比較基礎的演算法,它的作用不能忽視。所以,在把握這兩種演算法的時候應該特別注意。

③ 漢諾塔遞歸演算法是什麼

漢諾塔遞歸演算法是演算法分析。實現這個演算法可以簡單分為三個步驟:把n-1個盤子由A 移到 B;把第n個盤子由 A移到 C，把n-1個盤子由B 移到 C。

漢諾塔的來源及應用

相傳在古印度聖廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置64個金盤。

游戲的目標：把A桿上的金盤全部移到C桿上，並仍保持原有順序疊好。操作規則：每次只能移動一個盤子，並且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置於A、B、C任一桿上。

漢諾塔問題是用遞歸方法求解的一個典型問題，在實際教學中，可以在傳統教學方式的基礎上，利用計算機輔助教學進行演算法的模擬演示教學，使學生更容易接受和理解遞歸演算法的思想，不但能提高學生的學習興趣，而且還能取得較好的教學效果。

④ 什麼是遞歸演算法

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

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

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

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

⑤ 有人能幫我解釋一下什麼是遞歸法嗎

打個比方吧，遞歸法好比是一個軍隊要通過一個迷宮，到了第一個分岔口，有3條路，將軍命令3個小隊分別去探哪條路能到出口，3個小隊沿著3條路分別前進，各自到達了路上的下一個分岔口，於是小隊長再分派人手各自去探路——只要人手足夠（對照而言，就是計算機的堆棧足夠），最後必將有人找到出口，從這人開始只要層層上報直屬領導，最後，將軍將得到一條通路。所不同的是，計算機的遞歸法是把這個並行過程串列化了。

⑥ 怎樣才能深刻理解遞歸和回溯

遞歸是一種演算法結構，回溯是一種演算法思想，一個遞歸就是在函數中調用函數本身來解決問題，回溯就是通過不同的嘗試來生成問題的解，有點類似於窮舉，但是和窮舉不同的是回溯會「剪枝」，意思就是對已經知道錯誤的結果沒必要再枚舉接下來的答案了，比如一個有序數列1,2,3,4,5，要找和為5的所有集合，從前往後搜索我選了1，然後2，然後選3 的時候發現和已經大於預期，那麼4,5肯定也不行，這就是一種對搜索過程的優化。
回溯分析是追蹤決策的特性之一。 是指對原始決策的產生機制、決策內容、主客觀環境等進行分析．從起點開始，按順序考察導致決策失誤的原因、問題的性質、失誤的程度等。
[演算法分析]
為了描述問題的某一狀態，必須用到它的上一狀態，而描述上一狀態，又必須用到它的上一狀態……這種用自已來定義自己的方法，稱為遞歸定義。例如：定義函數f(n)為：
f(n)=n*f(n－1) (n>0)
f(n)=1 (n=0)
則當0時，須用f(n-1)來定義f(n),用f(n-1-1)來定義f(n-1)……當n=0時，f(n)=1。
由上例我們可看出，遞歸定義有兩個要素：
（1）遞歸邊界條件。也就是所描述問題的最簡單情況，它本身不再使用遞歸的定義。
如上例，當n=0時，f(n)=1，不使用f(n-1)來定義。
（2）遞歸定義：使問題向邊界條件轉化的規則。遞歸定義必須能使問題越來越簡單。
如上例：f(n)由f(n-1)定義，越來越靠近f(0),也即邊界條件。最簡單的情況是f(0)=1。
遞歸演算法的效率往往很低, 費時和費內存空間. 但是遞歸也有其長處, 它能使一個蘊含遞歸關系且結構復雜的程序簡介精煉, 增加可讀性. 特別是在難於找到從邊界到解的全過程的情況下, 如果把問題推進一步,其結果仍維持原問題的關系, 則採用遞歸演算法編程比較合適.
遞歸按其調用方式分為: 1. 直接遞歸, 遞歸過程P直接自己調用自己; 2. 間接遞歸, 即P包含另一過程D, 而D又調用P.
遞歸演算法適用的一般場合為:
1. 數據的定義形式按遞歸定義.
如裴波那契數列的定義: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2.
對應的遞歸程序為:
Function fib(n : integer) : integer;
Begin
if n = 0 then fib := 1 { 遞歸邊界 }
else if n = 1 then fib := 2
else fib := fib(n-2) + fib(n-1) { 遞歸 }
End;
這類遞歸問題可轉化為遞推演算法, 遞歸邊界作為遞推的邊界條件.
2. 數據之間的關系(即數據結構)按遞歸定義. 如樹的遍歷, 圖的搜索等.
3. 問題解法按遞歸演算法實現. 例如回溯法等.
從問題的某一種可能出發, 搜索從這種情況出發所能達到的所有可能, 當這一條路走到" 盡頭 "
的時候, 再倒回出發點, 從另一個可能出發, 繼續搜索. 這種不斷" 回溯 "尋找解的方法, 稱作
" 回溯法 ".

[參考程序]
下面給出用回溯法求所有路徑的演算法框架. 注釋已經寫得非常清楚, 請讀者仔細理解.
Const maxdepth = ????;
Type statetype = ??????; { 狀態類型定義 }
operatertype = ??????; { 算符類型定義 }
node = Record { 結點類型 }
state : statetype; { 狀態域 }
operater :operatertype { 算符域 }
End;
{ 注: 結點的數據類型可以根據試題需要簡化 }
Var
stack : Array [1..maxdepth] of node; { 存當前路徑 }
total : integer; { 路徑數 }
Procere make(l : integer);
Var i : integer;
Begin
if stack[L-1]是目標結點 then
Begin
total := total+1; { 路徑數+1 }
列印當前路徑[1..L-1];
Exit
End;
for i := 1 to 解答樹次數 do
Begin
生成 stack[l].operater;
stack[l].operater 作用於 stack[l-1].state, 產生新狀態 stack[l].state;
if stack[l].state 滿足約束條件 then make(k+1);
{ 若不滿足約束條件, 則通過for循環換一個算符擴展 }
{ 遞歸返回該處時, 系統自動恢復調用前的棧指針和算符, 再通過for循環換一個算符擴展 }
{ 注: 若在擴展stack[l].state時曾使用過全局變數, 則應插入若干語句, 恢復全局變數在
stack[l-1].state時的值. }
End;
{ 再無算符可用, 回溯 }
End;
Begin
total := 0; { 路徑數初始化為0 }
初始化處理;
make(l);
列印路徑數total
End.

⑦ 什麼情況下可以利用遞歸來解決問題再寫遞歸程序時應注意是什麼

比如階乘，也就是說求n可以先求n-1，以此類推，到1，這類問題都可以用遞歸解決，菲波拉鍥數也可以遞歸。因為遞歸是總是調用自身解決問題，所以，必須有結束條件，否則會出問題，導致內存卡爆