学步园

 想测试下递归和非递归运行效率的差异，因此我把八皇后以同样算法用递归和非递归实现了一遍，测试结果如下：

问题规模较小时非递归效率稍高，但规模一大就完了。。 

递归与非递归相比，递归的优点有：代码简洁，可阅读性强。递归缺点，浪费空间。

测试的代码，比较简单：

#include<iostream><br /> #include<time.h><br /> using namespace std;<br /> int s=0,n;</p> <p>void queen() /*n皇后非递归*/<br /> {<br /> int i,p=0,*loca=new int[n];<br /> memset(loca,0,sizeof(int)*n);<br /> while(p>-1)<br /> {<br /> for(;loca[p]<n;)<br /> {<br /> if(p==n)<br /> {<br /> s++; p--; loca[p]++; continue;<br /> }<br /> for(i=0;i<p&&abs(loca[i]-loca[p])!=p-i&&loca[i]!=loca[p];i++);<br /> if(i==p)<br /> { p++; continue; }<br /> loca[p]++;<br /> }<br /> loca[p]=0;<br /> p--;<br /> loca[p]++;<br /> }</p> <p>}</p> <p>void queen1(int deep,int loca[]) /*n皇后递归*/<br /> {<br /> if(deep==n)<br /> { s++; return ; }<br /> for(loca[deep]=0;loca[deep]<n;loca[deep]++)<br /> {<br /> for(int i=0;i<deep&&loca[i]!=loca[deep]&&abs(loca[i]-loca[deep])!=deep-i;i++);<br /> if(i==deep)<br /> queen1(deep+1,loca);<br /> }<br /> }</p> <p>int main()<br /> {<br /> int a[200],b;<br /> while(cin>>n&&n)<br /> {<br /> s=0;<br /> b=clock();<br /> queen();<br /> cout<<"非递归找到"<<s<<"组解，用时:"<<clock()-b<<endl;<br /> s=0;<br /> b=clock();<br /> queen1(0,a);<br /> cout<<"递归找到"<<s<<"组解，用时:"<<clock()-b<<endl;<br /> }</p> <p> return 0;<br /> }

测试环境

CPU: P4 2.93G

MEM: 1G DDR

OS  :  WIN XP

IDE :  VC++ 6.0