遞歸的非遞歸演算法
① 有些遞歸程序是不能用非遞歸演算法實現的
c語言所有遞歸都可以用非遞歸演算法實現，最典型的就是迭代法，有時比遞歸更容易理解。至於遞歸中的形式參數是自動變數，沒明白樓主的意思，形參就是形參啊，形參變數也是變數，其內存分配在棧區，隨著函數的結束，其內存也會被釋放，形參的生命周期與函數生命周期相同哈（同生共死）
② 利用棧將二叉樹遞歸演算法轉化為非遞歸演算法
#define
struct_sizes
20
#define
adds
10
typedef
struct
bitnode//二叉樹的定義
{
int
data;//二襪昌叉樹元素數據類型
struct
bitnode
*lchild,*rchild;//左右孩子
}*bitree;
typedef
struct
//順序棧的定義
{
bitree
*base;//棧底指針
bitree
*top;//棧頂指針
int
stacksize;
}sqstack;
int
initstack(sqstack
&S)//新建一個空棧
{
S.base=(bitree
*)malloc(struct_sizes*sizeof(bitree));
if(!S.base)return
0;
S.top
=
S.base;
S.stacksize
=
struct_sizes;
return
1;
}//initstack
int
stackempty(sqstack
S)
//判斷棧是否為空
{
if(S.base==S.top)return
1;
else
return
0;
}
int
push(sqstack
&S,bitree
e)//進棧
{
if(S.top
-
S.base
>=
S.stacksize)//棧滿重新分配空間
{
S.base
=
(bitree
*)realloc(S.base,(S.stacksize
+
adds)
*
sizeof
(bitree));
if(!S.base)return
0;
S.top
=
S.base
+
S.stacksize;
S.stacksize
+=
adds;
}
*(S.top++)=e;
return
1;
}//push
int
pop(sqstack
&S,bitree
&e)//出棧
{
if(S.top
==
S.base)return
0;
e
=
*
--S.top;
return
1;
}//pop
int
gettop(sqstack
S,bitree
&e)//取棧頂元素
{
if(S.top
==
S.base)
return
0;
e
=
*(S.top
-
1);
return
1;
}//gettop
int
mid_travel(bitree
T)//遞歸二叉樹中序遍歷
{
if(!T)return
0;
else
{
if(T->lchild)mid_travel(T->侍答lchild);
printf("
%d",T->data);
if(T->rchild)mid_travel(T->rchild);
}
return
1;
}
int
mid_norecursion(bitree
T)
//中序遍歷二叉樹T的非遞告談扒歸演算法，列印每個數據
{
sqstack
S;
bitree
p;
if(!T)return
0;
initstack(S);push(S,T);//根指針進棧
while(!stackempty(S))
{
while(gettop(S,p)&&p)push(S,p->lchild);//向左走到盡頭
pop(S,p);
//空指針退棧
if(!stackempty(S))//訪問結點，向右一步
{
pop(S,p);printf("
%d",p->data);
push(S,p->rchild);
}
}
return
1;
}
③ 遞歸與非遞歸
首先要理解遞歸本身其實是一項非常重要的演算法技巧。
遞歸滿足兩個條件：
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;
}
除了上面這兩種笑擾碰方法外，還可以使用一種迭代的方法實現遞歸到非遞歸的處理．
④ 程序的遞歸演算法與非遞歸有什麼區別
遞歸演算法是一種直接或者間接地調用自身的演算法。
在計算機編寫程序中，遞歸演算法對解決一大類問題是十分有效的，它往往使演算法的描述簡潔而且易於理解。
遞歸就是在過程或函數里調用自身。
在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
遞歸演算法解題通常顯得很簡潔，但遞歸演算法解題的運行效率較低。所以一般不提倡用遞歸演算法設計程序。
在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出。
⑤ 程序的遞歸演算法與非遞歸的區別
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. 總結： 直接引用《演算法設計與分析（第二版）》里的一段話： 結構清晰，可讀性強，而且容易用數學歸納法來證明演算法的正確性，而且它為設計演算法，調試程序帶來很大方便。 然而遞歸演算法的運行效率較低，無論是耗費的計算時間還是佔用的存儲空間都比非遞歸演算法要多 僅僅是機械地模擬還不能達到減少計算時間和存儲空間的目的。因此，還需要根據具體程序和特點對遞歸調用的工作棧進行簡化，盡量減少棧的操作，壓縮棧存儲以達到節省計算時間和存儲空間的目的。
⑥ 遞歸演算法跟非遞歸演算法的區別
遞歸演算法是一種分而治之的方法，簡單的說就是調用自己本身；能把復雜的問題化為簡單來解決；但是執行的效率比較低，所以一般分析問題用遞歸，實際解決問題用非遞歸。
⑦ 非遞歸演算法比較有哪些主要的優點和缺點
非遞歸演算法和遞歸演算法的主要優缺點：
非遞歸演算法的優點：如果需要處理的數據規模比較大的時候，適合使用非遞歸演算法。缺點：程序代碼的可讀性差一些。
遞歸演算法的優點：程序代碼的可讀性要比非遞歸演算法的好，如果需要處理的數據量比較小的時候，適合使用遞歸演算法。缺點：當需要處理的數據規模比較大的時候，就不適合使用遞歸演算法了。因為遞歸演算法涉及到對堆棧的頻繁操作（入棧、出棧），系統效率會很低，嚴重的時候會導致系統崩潰。
⑧ 二叉樹先序遍歷遞歸演算法和非遞歸演算法本質區別
在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
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;
}
⑨ 遞歸演算法向非遞歸如何轉化
由於遞歸在解決問題時，效率較低下，但是理解起來比較好。所以有些問題我們是先用遞歸設計出來演算法，之後再用非遞歸的方法來書寫正式的代碼。一般有兩種方法轉化的方法。比較簡單的是直接利用中間變數和循環的，比較復雜的是利用棧來存儲結果，先依次進棧，之後再把後的到的結果依次出棧，直到棧為空。。。
⑩ 遞歸演算法與非遞歸演算法的比較
否，一般而言非遞歸演算法更有效；但很多時候遞歸演算法容易實現，編程簡單。