递归算法非递归
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);
}