遞歸演算法非遞歸
A. 遞歸演算法向非遞歸如何轉化
由於遞歸在解決問題時，效率較低下，但是理解起來比較好。所以有些問題我們是先用遞歸設計出來演算法，之後再用非遞歸的方法來書寫正式的代碼。一般有兩種方法轉化的方法。比較簡單的是直接利用中間變數和循環的，比較復雜的是利用棧來存儲結果，先依次進棧，之後再把後的到的結果依次出棧，直到棧為空。。。
B. 有些遞歸程序是不能用非遞歸演算法實現的
c語言所有遞歸都可以用非遞歸演算法實現，最典型的就是迭代法，有時比遞歸更容易理解。至於遞歸中的形式參數是自動變數，沒明白樓主的意思，形參就是形參啊，形參變數也是變數，其內存分配在棧區，隨著函數的結束，其內存也會被釋放，形參的生命周期與函數生命周期相同哈（同生共死）
C. 非遞歸演算法比較有哪些主要的優點和缺點
非遞歸演算法和遞歸演算法的主要優缺點：
非遞歸演算法的優點：如果需要處理的數據規模比較大的時候，適合使用非遞歸演算法。缺點：程序代碼的可讀性差一些。
遞歸演算法的優點：程序代碼的可讀性要比非遞歸演算法的好，如果需要處理的數據量比較小的時候，適合使用遞歸演算法。缺點：當需要處理的數據規模比較大的時候，就不適合使用遞歸演算法了。因為遞歸演算法涉及到對堆棧的頻繁操作（入棧、出棧），系統效率會很低，嚴重的時候會導致系統崩潰。
D. 二叉樹先序遍歷遞歸演算法和非遞歸演算法本質區別
在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
1）入棧，主要是先頭結點入棧，然後visit此結點
2）while，循環遍歷當前結點，直至左孩子沒有結點
3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）
先看符合此思想的演算法：
[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此時棧已空，就有問題
}
pBiNode = pBiNode->rchild;
}
return 0;
}
E. 程序的遞歸演算法與非遞歸的區別
1、遞歸和非遞歸（用棧） 非遞歸（用棧），也用到棧函數了，和遞歸就沒多大區別了! 每次遞歸進棧出棧，非遞歸（用棧）的每次調用棧函數也是進棧出棧。主要是在非遞歸（用棧）中，它的棧函數里比遞歸多了些賦值語句。。。所以效率上，非遞歸（用棧）比遞歸差。 只不過，遞歸越深，佔用棧空間越多。非遞歸（用棧），佔用的棧空間少。如果，遞歸的深度還沒達到超出棧空間的程度，那麼遞歸比非遞歸（用棧）好。 如果是非遞歸（不用棧），當然是非遞歸最好。 在下面的這個例子（解決「整數劃分問題」）中，說明了如果只是用棧機械的模擬，得到的結果只是： 空間不變（事實上，非遞歸應該多一些），而非遞歸的時間數倍的增加。。 感興趣的朋友運行就知道了 #include<iostream> #include<stack> #include<ctime> using namespace std; //---------------------------遞歸演算法 int q(int n,int m) { if((n<1) || (m<0)) return 0; if((n==1) ||(m==1)) return 1; if(n<m) return q(n,n); if(n==m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); } int q(int num) { return q(num,num); } struct Point { int n,m; Point(int _n,int _m){ n=_n; m=_m;} }; //-------------------------非遞歸演算法 int _q(int n,int m) { int sum=0; Point tmp(n,m); stack<Point> s; s.push (tmp); while(!s.empty()) { tmp=s.top(); n=tmp.n; m=tmp.m; s.pop(); if((n<1) || (m<0)) ++sum; else if((n==1) ||(m==1)) ++sum; else if(n<m) s.push(Point(n,n)); else if(n==m) { ++sum; s.push(Point(n,m-1)); } else { s.push(Point(n,m-1)); s.push(Point(n-m,m)); } } return sum; } int _q(int num) { return _q(num,num); } int main() { int num; unsigned int p; do{ cout<<"Input a num:"; cin>>num; p=clock(); cout<<" 遞歸： "<<q(num)<<endl; cout<<"\t\t用時:"<<clock()-p<<endl; p=clock(); cout<<"非遞歸： "<<_q(num)<<endl; cout<<"\t\t用時:"<<clock()-p<<endl<<endl; }while(num); return 0; } 2. 如果非遞歸不是用棧做的 這里有一個網友做的漢諾塔問題的非遞歸解法 看了真讓人汗顏 這樣的規律都有人發現 下載地址是： http://wenku..com/view/cfd56b3610661ed9ad51f3f9.html 此演算法不是用大家以前熟悉的遞歸演算法 雖然沒運行 可以猜想 這個程序的空間和時間效率毫無疑問會大幅度提高。 3. 總結： 直接引用《演算法設計與分析（第二版）》里的一段話： 結構清晰，可讀性強，而且容易用數學歸納法來證明演算法的正確性，而且它為設計演算法，調試程序帶來很大方便。 然而遞歸演算法的運行效率較低，無論是耗費的計算時間還是佔用的存儲空間都比非遞歸演算法要多 僅僅是機械地模擬還不能達到減少計算時間和存儲空間的目的。因此，還需要根據具體程序和特點對遞歸調用的工作棧進行簡化，盡量減少棧的操作，壓縮棧存儲以達到節省計算時間和存儲空間的目的。
F. 遞歸演算法跟非遞歸演算法的區別
遞歸演算法是一種分而治之的方法，簡單的說就是調用自己本身；能把復雜的問題化為簡單來解決；但是執行的效率比較低，所以一般分析問題用遞歸，實際解決問題用非遞歸。
G. 所有用遞歸演算法的能不能都用非遞歸演算法實現
用遞歸演算法可以使程序結構清晰,可讀性好,但是它的運行效率很低,而且會占據很大存儲空間,因此有時希望在程序中消除遞歸.因為在計算機內遞歸演算法實際上是用一個工作棧來實現的,所以所有的遞歸演算法理論上來說是可以用非遞歸演算法實現,我們可以用一個棧來模擬遞歸演算法
H. 程序的遞歸演算法與非遞歸有什麼區別
遞歸演算法是一種直接或者間接地調用自身的演算法。
在計算機編寫程序中，遞歸演算法對解決一大類問題是十分有效的，它往往使演算法的描述簡潔而且易於理解。
遞歸就是在過程或函數里調用自身。
在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
遞歸演算法解題通常顯得很簡潔，但遞歸演算法解題的運行效率較低。所以一般不提倡用遞歸演算法設計程序。
在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出。
I. 如何將遞歸轉換為非遞歸
轉化的方法一般有以下兩種，一是遞歸轉化為遞推，用迭代的思想去求解，程序效率要高得多，如求Fabonacci數列問題；二是自己定義堆棧來模擬遞歸的過程，但會減低程序的可讀性，如漢諾塔問題。
第一種方法比較簡單，下面重點講一下第二種方法。
設P是一個遞歸演算法，假定P中共有m個值參和局部變數，共有t處遞歸調用P的語句，則把P改寫成一個非遞歸演算法的一般規則為：
1、 定義一個棧S，用來保存每次遞歸調用前值參和局部變數的當前值以及調用後的返回地址。即S應該含有m+1個域，且S的深度必須足夠大，使得遞歸過程中不會發生棧溢出。
2、 定義t+2個語句標號，其中用一個標號標在原演算法中的第一條語句上，用另一個標號標在作返回處理的第一條語句上，其餘t個標號標在t處遞歸調用的返回地址，分別標在相應的語句上。
3、 把每一個遞歸調用語句改寫成如下形式：
（1） 把值參和局部變數的當前值以及調用後的返回地址壓入棧；
（2） 把值參所對應的實在參數表達式的值賦給值參變數；
（3） 無條件轉向原演算法的第一條語句；
4、 在演算法結束前增加返回處理，當棧非空時做：
（1） 出棧；
（2） 把原棧頂中前m個域的值分別賦給各對應的值參和局部變數；
（3） 無條件轉向由本次返回地址所指定的位置；
5、 增設一個同棧S的元素類型相同的變數，作為進出棧的緩沖變數，對於遞歸函數，還需要再增設一個保存函數值中間結果的臨時變數，用這個變數替換函數體中的所有函數名，待函數結束之前，在把這個變數的值賦給函數名返回。
6、 在原演算法的第一條語句之前，增加一條把棧置空的語句。
7、 對於遞歸函數而言，若某條賦值語句中包含兩處或多處遞歸調用（假設為n處），則應首先把它拆成n條賦值語句，使得每條賦值語句只包含一處遞歸調用，同時對增加的n-1條賦值語句，要增設n-1個局部變數，然後按以上六條規則轉換成非遞歸函數。
struct record{
node* a;
int state;
record(node* a,int state):a(a),state(state){}
};
void non_recursive_inorder(){
stack<record> s;
node* cur=root; //初始化狀態
int state=0;
while(1){
if(!cur){ //如果遇到null結點，返回上一層
if(cur == root)break;//如果沒有上一層，退出循環
cur=s.top().a;
state=s.top().state; //返回上層狀態
s.pop();
}else if(state == 0){ //狀態位0，執行第一個遞歸inorder(cur->left);
s.push(record(cur,1));//保存本層狀態
cur=cur->left; //更新到下層狀態
state=0;
}else if(state == 1){ //狀態為1，執行print和inorder(cur->right)
printf("%d ",cur->x);
s.push(record(cur,2)); //保存本層狀態
cur=cur->right; //進入下層狀態
state=0;
}else if(state == 2){ //狀態2，函數結束，返回上層狀態
if(cur == root)break; //初始結點的退出狀態，遍歷結束
cur=s.top().a; //返回上層狀態
state=s.top().state;
s.pop();
}
}
putchar(10);
}