遞歸演算法轉換成非遞歸代碼

Ⅰ (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;
}
除了上面這兩種方法外，還可以使用一種迭代的方法實現遞歸到非遞歸的處理．

Ⅱ 在C語言中什麼叫遞歸

遞歸：就是自己調自己，但是沒終止條件會死循環，所以你的遞歸代碼里有結束自調自的條件，這樣就創造了有限次的循環（代碼中你看不到for或foreach但是有循環發生）

Ⅲ 所有的遞歸程序都能轉化為非遞歸么

是的，所有遞歸都可以換成非遞歸，效率方面不一定能提高，看具體演算法。

Ⅳ python漢諾塔非遞歸

python漢諾塔非遞歸，運用list和function知識的解答

無論stack還是recursion都是從漢諾塔的原理去解決問題，但如果已經想清楚漢諾塔的原理，其實只用把答案print出來就行了

先找規律：

一層：A-->C

兩層：A-->B

-------

A-->C

-------

B-->C

三層：A-->C

A-->B

C-->B

-------

A-->C

-------

B-->A

B-->C

A-->C

注意到n層漢諾塔有(2**n) - 1 個步驟，而中間的一步（兩個分割線之間）都是「A-->C」，中間的這一步將這一層漢諾塔的解分為上下兩個部分

仔細觀察，上面一部分是將上一層的解中所有的B，C交換，下面一部分是將上一層的解中所有的A，B交換

例如第二層是：

A-->B

A-->C

B-->C

第三層上部分就將第二層的解的C換成B，B換成C，即得出：

A-->C

A-->B

C-->B

第三層下部分就將第二層的解的A換成B，B換成A，即得出：

B-->A

A-->C

C-->B

這個規律同樣適用於第一層，和以後的所有層

然後就好辦了，代碼如圖：

代碼

其中convertAB,convertBC就是AB交換，BC交換的函數，這兩個函數可以自己定義，用中間變數即可

Ⅳ python-027-遞歸-求序列最大值、計算第n個調和數、轉換字元到整數

遞歸，emmmmmmm，擁有一種魅力，接近人的立即思維，容易理解，又不容易理解。

遞歸演算法的優點： 它使我們能夠簡潔地利用重復結構呈現諸多問題。通過使演算法描述以遞歸的方式利用重復結構，我們經常可以避開復雜的案例分析和嵌套循環。這種演算法會得出可讀性更強的演算法描述，而且十分有效。

但是 ，遞歸的使用要根據相應的成本來看，每次遞歸python解釋器都會給一個空間來記錄函數活動狀態。但是有時候內存成本很高，有時候將遞歸演算法轉為非遞歸演算法是一種好辦法。

當然我們可以換解釋器、使用堆棧數據結構等方法，來管理遞歸的自身嵌套，減小儲存的活動信息，來減小內存消耗。

最近演算法學到了遞歸這一塊，寫了三個課後習題：

給一個序列S，其中包含n個元素，用遞歸查找其最大值。

輸出：

調和數：Hn = 1 + 1/2 + 1/3 + ··· + 1/n

輸出：

例如："12345"<class 'str'> 轉換為12345<class 'int'>

輸出：

遞歸分為線性遞歸、二路遞歸、多路遞歸。