递归的非递归算法
① 有些递归程序是不能用非递归算法实现的
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;
}
⑨ 递归算法向非递归如何转化
由于递归在解决问题时，效率较低下，但是理解起来比较好。所以有些问题我们是先用递归设计出来算法，之后再用非递归的方法来书写正式的代码。一般有两种方法转化的方法。比较简单的是直接利用中间变量和循环的，比较复杂的是利用栈来存储结果，先依次进栈，之后再把后的到的结果依次出栈，直到栈为空。。。
⑩ 递归算法与非递归算法的比较
否，一般而言非递归算法更有效；但很多时候递归算法容易实现，编程简单。