遞歸演算法做題思路

Ⅰ (1-2+3-4+5-6+7-8+9)用遞歸方法怎麼寫

首先要理解遞歸本身其實是一項非常重要的演算法技巧。
遞歸滿足兩個條件：
1，不斷調用函數本身，也就是遞歸函數。
2，調用是有限的，也就是遞歸出口。
為了理解方便，下面是用一個最簡單的例子：求n的階乘。
n!(階乘)定義：
n!數學意思為n!
=
n*(n-1)!
&
1!=1;
其實根據上面遞歸定義結合分析下就可以n階乘的遞歸演算法：
1,構造一個遞歸函數,不斷乘以自身和使用自身減一後調用同樣函數．
2,定義出口，當函數參數等於1時結束;
如果用iso
c++語言描述如下：
int
factorial(int
n){
if(
n
>
1){
return
n*factorial(n-1);//遞歸函數調用
}
else
if(n
==
1){
return
1;
//遞歸出口
}
else{
return
error;//報告輸入錯誤
}
}
這里討論主要的不是上面這個簡單的例子，而是下面的一些改良．
因為遞歸設計大量的堆棧操作，所以一般都會考慮將遞歸轉為非遞歸來執行．
這里用上面這個程序作一個分析例子來分析．
假設這里執行factorial(4)，那麼程序會按照下面方式來執行：
(1)執行factorial(4)判斷n
>
1執行factorial(3),並且將factorial(4)函數相關信息存入一個堆棧．
(2)執行factorial(3)判斷n
>
1執行factorial(2),並且將factorial(3)函數相關信息存入一個堆棧．
(3)執行factorial(2)判斷n
>
1執行factorial(1),並且將factorial(2)函數相關信息存入一個堆棧．
(4)執行factorial(1)判斷n
==
1執行返回1;
(5)將factorial(2)函數從堆棧中彈出，執行2*1，並且返回2．
(6)將factorial(3)函數從堆棧中彈出，執行2*3，並且返回6．
(7)將factorial(4)函數從堆棧中彈出，執行6*4，並且返回24．
如下圖所示：
factorial(4)
-->factorial(3);
-->factorial(2);
-->factorail(1);
<--factorail(1);
<--factorial(2);
<--factorial(3);
<--結果
可以看到中間涉及的堆棧操作是很大的開銷，每次需要保存當前函數的所有信息．
為了避免這樣情況，可以使用下面這幾種方法來實現遞歸到非遞歸的轉換．
(1)
循環方法
循環方法是所有遞歸到非遞歸的轉換中最理想的方法，可以將開銷減少到最小．
不過也是分析起來最復雜的，對於簡單的遞歸可以用這樣的方法來處理．
例如：factorial計算
這里回到n!(階乘)定義上面來分析，這里將n!數學意思為n!
=
n*(n-1)!
&
1!=1;做一個擴展可以到到n!另外一個表示方法n!
=
n*(n-1)*(n-2)*....*1;
這樣就可以很容易得到另外一個定義：
n!表示執行n次循環計算一個增量k，初始k=1和結果t=1;每次t乘以k++的值.
iso
c++實現代碼如下：
factorial(int
n){
int
k
=
1
;//增量
int
t
=
1
;//臨時結果
while(k!=n){
t*=k;
k++;
}
return
t;
}
這樣可以避免遞歸帶來的大量堆棧操作．
(2)
自定義堆棧
對於復雜邏輯的堆棧操作，需要藉助外部堆棧來實現．
因為對於所有的遞歸操作最後分析出來都是形成的一顆樹形結構．
下面是一個遞歸實現factorial的一個方法，雖然在這個程序中對比循環來相對復雜，不過對於一些不能分析出來循環的遞歸操作來說自定義堆棧的方法可以達到空間開銷可控．
factorial(int
n){
stack
s;
int
t
=
1;//臨時變數
s.push(n);
while(s.top()!=1)[
t
*=
s.top();
s.push(s.top()-1);
s.pop();
}
return
t;
}
除了上面這兩種方法外，還可以使用一種迭代的方法實現遞歸到非遞歸的處理．

Ⅱ 遞歸主方法

遞歸的主要方法是什麼？

一、遞歸演算法
遞歸演算法（英語：recursion algorithm）在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用於解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念。絕大多數編程語言支持函數的自調用，在這些語言中函數可以通過調用自身來進行遞歸。計算理論可以證明遞歸的作用可以完全取代循環，因此在很多函數編程語言（如Scheme）中習慣用遞歸來實現循環。
二、遞歸程序
在支持自調的編程語言中，遞歸可以通過簡單的函數調用來完成，如計算階乘的程序在數學上可以定義為：

這一程序在Scheme語言中可以寫作：
1
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))
不動點組合子
即使一個編程語言不支持自調用，如果在這語言中函數是第一類對象（即可以在運行期創建並作為變數處理），遞歸可以通過不動點組合子（英語：Fixed-point combinator）來產生。以下Scheme程序沒有用到自調用，但是利用了一個叫做Z 運算元（英語：Z combinator）的不動點組合子，因此同樣能達到遞歸的目的。
1
(define Z (lambda (f) ((lambda (recur) (f (lambda arg (apply (recur recur) arg)))) (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))(define fact (Z (lambda (f) (lambda (n) (if (<= n 0) 1 (* n (f (- n 1))))))))
這一程序思路是，既然在這里函數不能調用其自身，我們可以用 Z 組合子應用(application)這個函數後得到的函數再應用需計算的參數。
尾部遞歸
尾部遞歸是指遞歸函數在調用自身後直接傳回其值，而不對其再加運算。尾部遞歸與循環是等價的，而且在一些語言（如Scheme中）可以被優化為循環指令。 因此，在這些語言中尾部遞歸不會佔用調用堆棧空間。以下Scheme程序同樣計算一個數字的階乘，但是使用尾部遞歸：
1
(define (factorial n) (define (iter proct counter) (if (> counter n) proct (iter (* counter proct) (+ counter 1)))) (iter 1 1))
三、能夠解決的問題
數據的定義是按遞歸定義的。如Fibonacci函數。
問題解法按遞歸演算法實現。如Hanoi問題。
數據的結構形式是按遞歸定義的。如二叉樹、廣義表等。
四、遞歸數據
數據類型可以通過遞歸來進行定義，比如一個簡單的遞歸定義為自然數的定義：「一個自然數或等於0，或等於另一個自然數加上1」。Haskell中可以定義鏈表為：
1
data ListOfStrings = EmptyList | Cons String ListOfStrings
這一定義相當於宣告「一個鏈表或是空串列，或是一個鏈表之前加上一個字元串」。可以看出所有鏈表都可以通過這一遞歸定義來達到。

Ⅲ 簡述遞歸問題的求解過程

遞歸演算法的執行過程分遞推和回歸兩個階段。在遞推階段，把較復雜的問題（規模為n）的求解推到比原問題簡單一些的問題（規模小於n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說，為計算fib(n)，必須先計算fib(n-1)和fib(n-2)，而計算fib(n-1)和fib(n-2)，又必須先計算fib(n-3)和fib(n-4)。依次類推，直至計算fib(1)和fib(0)，分別能立即得到結果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數fib中，當n為1和0的情況。
在回歸階段，當獲得最簡單情況的解後，逐級返回，依次得到稍復雜問題的解，例如得到fib(1)和fib(0)後，返回得到fib(2)的結果，……，在得到了fib(n-1)和fib(n-2)的結果後，返回得到fib(n)的結果。
在編寫遞歸函數時要注意，函數中的局部變數和參數只是局限於當前調用層，當遞推進入「簡單問題」層時，原來層次上的參數和局部變數便被隱蔽起來。在一系列「簡單問題」層，它們各有自己的參數和局部變數。

Ⅳ java中遞歸演算法是什麼怎麼算的

一、遞歸演算法基本思路：

Java遞歸演算法是基於Java語言實現的遞歸演算法。遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。遞歸演算法實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法表示問題的解。遞歸往往能給我們帶來非常簡潔非常直觀的代碼形式，從而使我們的編碼大大簡化，然而遞歸的思維確實跟我們的常規思維相逆的，通常都是從上而下的思維問題，而遞歸趨勢從下往上的進行思維。

二、遞歸演算法解決問題的特點：

【1】遞歸就是方法里調用自身。

【2】在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。

【3】遞歸演算法代碼顯得很簡潔，但遞歸演算法解題的運行效率較低。所以不提倡用遞歸設計程序。

【4】在遞歸調用的過程中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等，所以一般不提倡用遞歸演算法設計程序。

【5】在做遞歸演算法的時候，一定把握出口，也就是做遞歸演算法必須要有一個明確的遞歸結束條件。這一點是非常重要的。其實這個出口就是一個條件，當滿足了這個條件的時候我們就不再遞歸了。

三、代碼示例：

publicclassFactorial{

//thisisarecursivefunction

intfact(intn){

if(n==1)return1;

returnfact(n-1)*n;

}}

publicclassTestFactorial{publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

Factorialfactorial=newFactorial();

System.out.println("factorial(5)="+factorial.fact(5));

}
}

代碼執行流程圖如下：

此程序中n=5就是程序的出口。

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

hanot (n-1,b,a,c);（解釋：在把B塔上的(n-1))個藉助A塔移動到C塔）

為了實現 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。

遞歸，就是在運行的過程中調用自己。

構成遞歸需具備的條件：

1，子問題須與原始問題為同樣的事，且更為簡單；

2，不能無限制地調用本身，須有個出口，化簡為非遞歸狀況處理。

在數學和計算機科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，並規定其他所有情況都能被還原為其基本情況。

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