一个非递归程序

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

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

/*斐波那契数列，递归运行时程序是逆推的，所以循环时n的取值要反过来做，即从小到大。
因为每一次运算后的新值与其前一个值会作为之后运算的数据，也就是说参与运算的数据编码要向后移一个，如果用三个变量f1、f2、f3来分别表示连续的三个数的话：f3=f1+f2，之后原f2变为新f1、原f3变为新f2后再参与下一项的计算。
程序改为：
*/
int f(int n)
{
int f1,f2,f3;
int i=0;

for(i=0;i<=n;i++)
{
if(i==1 ||i==0)
{
f1=1;
f2=1;
}
else
{
f3=f1+f2;
f1=f2;
f2=f3;
}
}
return f3;
}

#include "stdafx.h"
#include <stack>
#include <iostream>
using namespace std;

const int N = 3; //数组个数
const int M =4; //每个数组元素

int a[N][M] = {{1,2,3,4},{2,3,4,5},{3,4,5,6}};

int Sta[N]={0};

bool IsStaHasZero()
{
for(int i =0;i<N;i++)
{
if(Sta[i]==0)
{
return true;
}
}

return false;
}

void AdjustSta()
{
//Sta中不应该有0，如果有，那么进行调整

while(IsStaHasZero())
{
for(int i=N-1;i>0;i--)
{
if(Sta[i] ==0)
{
Sta[i-1] = Sta[i-1]-1;

//j到N都重置为M
for(int j =i;j<N;j++)
{
Sta[j] =M;
}
}
}
}
}

int Count =1;
int _tmain(int argc, _TCHAR* argv[])
{
//初始化
for(int i =0;i<N;i++)
{
Sta[i]=M;
}

//第一个问题，肯定是M^N种组合，直接for循环遍历即可
while(Sta[0]!=0)
{
//输出数据
for(int i =0;i<N;i++)
{
cout<<a[i][Sta[i]-1]<<" ";
}

Sta[N-1] = Sta[N-1]-1;

AdjustSta();

cout<<Count++<<endl;
}

getchar();

return 1;
}

第二个问题在输出的地方改为和判断，如果相等就输出即可，代码我不写了

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}
BiTNode,*BiTree;
typedef struct SqStack
{
BiTNode *base;
BiTNode *top;
int stacksize;
}
SqStack;
void InitStack(SqStack *S)
{
S->base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *S,BiTNode e)
{
if(S->top-S->base>=S->stacksize)
{
S->base=(BiTNode*)realloc(S->base,
(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*(S->top)=e;
S->top++;
}
BiTNode Pop(SqStack *S)
{
S->top --;
return *S->top;

}
int StackEmpty(SqStack *S)
{
if(S->top == S->base )
return 1;
else
return 0;
}
BiTree CreateBiTree()
{
char p;BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=p;
T->lchild=CreateBiTree(T->lchild);
T->rchild=CreateBiTree(T->rchild);
}
return (T);
}
void PreOrder(BiTree T)//先序
{
SqStack S;
BiTree p=T;
InitStack(&S);
if(p)
Push(&S,*p);
while(!StackEmpty(&S))
{
p=(BiTNode *)malloc(sizeof(BiTNode));
*p=Pop(&S);
printf("%c",p->data);
if(p->rchild)
Push(&S,*p->rchild);
if(p->lchild)
Push(&S,*p->lchild);
}
}

void InOrder(BiTree T)//中序
{
SqStack S;
BiTree p=T;
InitStack(&S);
while(p||!StackEmpty(&S))
{
if(p)
{
Push(&S,*p);
p=p->lchild;
}
else
{
p=(BiTNode *)malloc(sizeof(BiTNode));
*p=Pop(&S);
printf("%c",p->data);
p=p->rchild;
}
}
}

void PostOrder(BiTree T)//后序
{
SqStack S;
BiTNode p, *l, *r;
InitStack(&S);
Push(&S, *T);
while(!StackEmpty(&S))
{
p = Pop(&S);
l = p.lchild;
r = p.rchild;
if (l == NULL && r == NULL)
{
printf("%c", p.data);
}
else
{
p.lchild = NULL;
p.rchild = NULL;
Push(&S, p);
if (r != NULL) Push(&S, *r);
if (l != NULL) Push(&S, *l);
}
}
}

void main()
{
BiTree Ta;int a;
printf("请创建树");
Ta=CreateBiTree();
printf("请选择：\n");
scanf("%d",&a);
if(a==1)
{
printf("先序遍历:");
printf("\n");
PreOrder(Ta);
}
if(a==2)
{
printf("中序遍历:");
printf("\n");
InOrder(Ta);
}
if(a==3)
{
printf("后序遍历:");
printf("\n");
PostOrder(Ta);
}

}
我可以帮助你，你先设置我最佳答案后，我百度Hii教你。

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}
BiTNode,*BiTree;
typedef struct SqStack
{
BiTNode *base;
BiTNode *top;
int stacksize;
}
SqStack;
void InitStack(SqStack *S)
{
S->base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *S,BiTNode e)
{
if(S->top-S->base>=S->stacksize)
{
S->base=(BiTNode*)realloc(S->base,
(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*(S->top)=e;
S->top++;
}
BiTNode Pop(SqStack *S)
{
S->top --;
return *S->top;

}
int StackEmpty(SqStack *S)
{
if(S->top == S->base )
return 1;
else
return 0;
}
BiTree CreateBiTree()
{
char p;BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=p;
T->lchild=CreateBiTree(T->lchild);
T->rchild=CreateBiTree(T->rchild);
}
return (T);
}
void PreOrder(BiTree T)//先序
{
SqStack S;
BiTree p=T;
InitStack(&S);
if(p)
Push(&S,*p);
while(!StackEmpty(&S))
{
p=(BiTNode *)malloc(sizeof(BiTNode));
*p=Pop(&S);
printf("%c",p->data);
if(p->rchild)
Push(&S,*p->rchild);
if(p->lchild)
Push(&S,*p->lchild);
}
}

void InOrder(BiTree T)//中序
{
SqStack S;
BiTree p=T;
InitStack(&S);
while(p||!StackEmpty(&S))
{
if(p)
{
Push(&S,*p);
p=p->lchild;
}
else
{
p=(BiTNode *)malloc(sizeof(BiTNode));
*p=Pop(&S);
printf("%c",p->data);
p=p->rchild;
}
}
}

void PostOrder(BiTree T)//后序
{
SqStack S;
BiTNode p, *l, *r;
InitStack(&S);
Push(&S, *T);
while(!StackEmpty(&S))
{
p = Pop(&S);
l = p.lchild;
r = p.rchild;
if (l == NULL && r == NULL)
{
printf("%c", p.data);
}
else
{
p.lchild = NULL;
p.rchild = NULL;
Push(&S, p);
if (r != NULL) Push(&S, *r);
if (l != NULL) Push(&S, *l);
}
}
}

void main()
{
BiTree Ta;int a;
printf("请创建树");
Ta=CreateBiTree();
printf("请选择：\n");
scanf("%d",&a);
if(a==1)
{
printf("先序遍历:");
printf("\n");
PreOrder(Ta);
}
if(a==2)
{
printf("中序遍历:");
printf("\n");
InOrder(Ta);
}
if(a==3)
{
printf("后序遍历:");
printf("\n");
PostOrder(Ta);
}

}
你的串号我已经记下，采纳后我会帮你制作

---

锦江区15887899250： 一个非递归程序 - ？
昌薛复方： #include <stdio.h>#include <stdlib.h>#include <malloc.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree; typedef struct SqStack { BiTNode *base; ...

锦江区15887899250： 在二叉树T中,编写一个非递归程序输出该树的所有叶子结点.... - ？
昌薛复方： 在二叉树T中,编写一个非递归程序输出该树的所有叶子结点....汗马绝尘安外振中标青史 锦羊开泰富民清政展新篇 春满人间汗马绝尘安外振中标青史 锦羊开泰富民清政展新篇 春满人间

锦江区15887899250： C++:已知数列为:1,1,2,4,7,13,24,44,...,求数列的第 n项,用非递归程序写怎么写啊? - ？
昌薛复方：[答案] int a[3]={1,1,2}; int temp; for(int i=3;i

锦江区15887899250： 在二叉树T中,编写一个非递归程序输出该树的所有叶子结点. - ？
昌薛复方： 算法思路:需要辅助栈用后序遍历非递归算法,当遍历到该结点时,栈里面从栈顶到栈底的各元素就是该结点从其双亲开始依次往根回溯的所有祖先

锦江区15887899250： 汉诺塔非递归程序？
昌薛复方： void main(); #include <stdio.h> #define width (rings+1) void main() { int rings, last, next, x, z[500], s[3]; printf(＂how many rings? ＂); scanf(＂%d＂,&rings); for(x=1; x<=rings; x++) /* put rings on first peg */ z[x]=width-x; for(x=0; x<=2*width; x+=width) ...

锦江区15887899250： 求一个关于二叉树非递归遍历的程序 - ？
昌薛复方： #include #define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree; typedef struct SqStack { BiTNode *base; BiTNode *top; int stacksize; } SqStack; void ...

锦江区15887899250： c关于递归与非递归同样一个程序,什么时候用递归好,什么时候用非递 ？
昌薛复方： 调用函数是要付出一定开销的,比如上下文的保存与恢复,会不断有堆栈操作.所以会慢..递归就是不断地调用函数,只不过调用的是自己.一般来讲,同一个算法的非递归程序一定不慢于递归程序.适用环境嘛……这个不能明确划分...不如这样说吧~能不用递归的时候都不用递归,也就是有非递归算法的时候尽量避免递归.什么时候用递归呢?我想有这样几个吧~1.算法有比较简单的逻辑,比如阶乘,再比如遍历树2.不用递归就解不开的问题(这个解不开是指要花费不少多余的力气才能解开)3.你不想让别人看懂你写的程序4.你想炫耀你高超的编程技术

锦江区15887899250： 递归程序和非递归程序的优缺点是什么? ？
昌薛复方： 递归代码少,但占用资源.非递归与之相反~

锦江区15887899250： 求“八皇后 - ---非递归法”的程序？
昌薛复方： 数据结构 #include <iostream.h> #include <stdlib.h> #define True 1 #define False 0 using namespace std; int nQueen(int*a,int k,int n) { int i,j,conflict; if(k>=n) return True; for(i=0;i<n;i++) { conflict=False; for(j=0;j<k;j++) { if(i==a[j]||(k-j)==(i-a[j])||(k-j)==(a[...

锦江区15887899250： 编写一个非递归算法求出二叉搜索树中的关键字最小的元素 - ？
昌薛复方： int MIN(BSTree *T)// T为根结点指针 { if (T == NULL) return -1;// 代表空树 while (T->lchild != NULL) T = T->lchild; return T->data; }