什么叫递归和非递归(非递归和递归的区别)
递归与非递归
首先要理解递归本身其实是一项非常重要的算法技巧。
递归满足两个条件：
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;
}
除了上面这两种方法外，还可以使用一种迭代的方法实现递归到非递归的处理．
程序的递归算法与非递归的区别
递归算法是一种直接或者间接地调用自身的算法。
在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归就是在过程或函数里调用自身。
在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出。
C语言中，递归先序遍历和非递归先序遍历的有何区别?各自优缺点?
1、递归就是函数调用函数本身，运行起来就是函数嵌套函数，层层嵌套，所以函数调用、参数堆栈都是不小的开销，但是程序简单。
2、非递归就是不断地对参数入栈、出栈，省去了函数层层展开、层层调用的开销。虽然参数出入栈次数多了，但是一般都开辟固定的足够大的内存来一次性开辟、重复使用。
3、非递归是从堆栈的角度来编写程序，速度快，但代码复杂。
递归是从问题本身的逻辑角度来编写，虽然速度相对慢，但代码容易理解。
如果对速度要求不高，建议用递归方式。
4、摘录例子如下：
#include stdio.h
#include stdlib.h
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;//二叉树的节点类型
typedef struct QNode
{
BiTNode data;
struct QNode *next;
} QNode,*QueuePtr;//队列节点类型
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;//队列的头尾指针
void InitQueue(LinkQueue *Q)//创建队列
{
Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode));
Q-rear-next=NULL;
}
void EnQueue(LinkQueue *Q,BiTNode e)//入队操作
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
p-data=e;
p-next=NULL;
Q-rear-next=p;
Q-rear=p;
}
BiTNode DeQueue(LinkQueue *Q)//出对操作
{
BiTNode e;QueuePtr p;
p=Q-front-next;
e=p-data;
Q-front-next=p-next;
if(Q-rear==p)
Q-rear=Q-front;
free(p);
return (e);
}
int QueueEmpty(LinkQueue *Q)//判断队列是否为空
{
if(Q-front==Q-rear )
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)//先序
{
if(T!=NULL)
{
printf("%c",T-data);
PreOrder(T-lchild);
PreOrder(T-rchild);
}
}
void LevelOrder(BiTree T)//层次遍历
{
LinkQueue Q; BiTNode p;
InitQueue(Q);
EnQueue(Q,*T);
while(!QueueEmpty(Q))
{
p = DeQueue(Q);
printf("%c",p.data);
if(p.lchild!=NULL)
EnQueue(Q,*(p.lchild));
if(p.rchild!=NULL)
EnQueue(Q,*(p.rchild));
}
}
void main()
{
BiTree Ta;
Ta=CreateBiTree();
printf("层次遍历:");
printf("\n");
LevelOrder(Ta);
printf("\n");
printf("先序遍历:");
printf("\n");
PreOrder(Ta);
}
层次使用非递归的，用到队列
先序是用递归的
创建树使用先序递归建树
输入个例子：
abc**de*f**g***(注意*代表空格，因为空格你看不到就不好表示).
递归和非递归
事实上，在解决一些问题的时候，经常使用到递归函数。
万一哪天为了追求效率，非要写迭代呢。
考虑，递归其实是让系统来做栈的操作。
所以迭代，其实，就是我们来做系统本来要做的事情。
我们需要的是：正在 ** 操作的数据 ， PC**，记录当前程序运行到哪个位置，以确定下一步做什么。
但是往往，PC 不需要被记录。
为什么前序和中序遍历，不需要用PC呢？
而后序要。
看了前序，中序，后序的递归函数，没有看出什么差别。
差别就在于stack.pop()之后的操作有几种。
前序和中序，pop()之后都是直接打印出来，后面操作只有一种。
{
1.打印出来
}
但是后序，pop()的时候，有两种情况
{
1.node=node.right
2.node打印出来
}