程序的递归算法与非递归的区别

1、递归和非递归（用栈） 非递归（用栈），也用到栈函数了，和递归就没多大区别了! 每次递归进栈出栈，非递归（用栈）的每次调用栈函数也是进栈出栈。主要是在非递归（用栈）中，它的栈函数里比递归多了些赋值语句。。。所以效率上，非递归（用栈）比递归差。 只不过，递归越深，占用栈空间越多。非递归（用栈），占用的栈空间少。如果，递归的深度还没达到超出栈空间的程度，那么递归比非递归（用栈）好。 如果是非递归（不用栈），当然是非递归最好。 在下面的这个例子（解决“整数划分问题”）中，说明了如果只是用栈机械的模拟，得到的结果只是： 空间不变（事实上，非递归应该多一些），而非递归的时间数倍的增加。。 感兴趣的朋友运行就知道了 #include<iostream>#include<stack>#include<ctime>using namespace std//---------------------------递归算法 int q(int n,int m) { if((n<1) || (m<0)) return 0if((n==1) ||(m==1)) return 1if(n<m) return q(n,n)if(n==m) return q(n,m-1)+1return q(n,m-1)+q(n-m,m)} int q(int num) { return q(num,num)} struct Point { int n,mPoint(int _n,int _m){ n=_nm=_m} }//-------------------------非递归算法 int _q(int n,int m) { int sum=0Point tmp(n,m)stack<Point>ss.push (tmp)while(!s.empty()) { tmp=s.top()n=tmp.nm=tmp.ms.pop()if((n<1) || (m<0)) ++sumelse if((n==1) ||(m==1)) ++sumelse if(n<m) s.push(Point(n,n))else if(n==m) { ++sums.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 numunsigned int pdo{ cout<<"Input a num:"cin>>nump=clock()cout<<" 递归： "<<q(num)<<endlcout<<"\t\t用时:"<<clock()-p<<endlp=clock()cout<<"非递归： "<<_q(num)<<endlcout<<"\t\t用时:"<<clock()-p<<endl<<endl}while(num)return 0} 2. 如果非递归不是用栈做的 这里有一个网友做的汉诺塔问题的非递归解法 看了真让人汗颜 这样的规律都有人发胡颂兄现 下载地址是： http://wenku.baidu.com/view/cfd56b3610661ed9ad51f3f9.html 此算法不是用大家以前熟悉的递归算法 虽然没运行 可以猜想 这个程序的空间和时间效率毫无疑问会大幅度提高。 3. 总结： 直接引用《算法设计与分析（第二版）》里的一段话： 结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，而且它为设计算法，调试程序带来很大方便。 然而递归算法樱胡的运行效率较低，无论是耗费的计算时间还裤袭是占用的存储空间都比非递归算法要多 仅仅是机械地模拟还不能达到减少计算时间和存储空间的目的。因此，还需要根据具体程序和特点对递归调用的工作栈进行简化，尽量减少栈的 *** 作，压缩栈存储以达到节省计算时间和存储空间的目的。

1、“递归”是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现像.。在计算机编程里，递归指的是一个过程：函数不断引用自身，直到引用明敏的对象已知。

2、腊茄“迭代”的含义是：重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得轮槐察到的结果会作为下一次迭代的初始值。

---