递归算法的优缺点（递归程序和非递归程序的优缺点是什么）

本文目录

• 递归程序和非递归程序的优缺点是什么
• 一个递归算法必须包括什么
• 非递归算法比较有哪些主要的优点和缺点
• 什么是递归递归有什么用
• 递归的通俗解释是什么
• C语言递归有什么用处，又有什么缺点
• C语言中，递归先序遍历和非递归先序遍历的有何区别各自优缺点

递归程序和非递归程序的优缺点是什么

递归代码少，设计到递推和回归两个过程，逻辑理解困难， 务必避免调用层次过多，和调用堆栈使用的栈内存过大，可能导致stack overflow
非递归就是正常写法了，递归的都能改成非递归的
递归算法必须写的很精确，否则容易造成死循环

一个递归算法必须包括什么

递归算法包含的两个部分：

1、由其自身定义的与原始问题类似的更小规模的子问题（只有数据规模不同），它使递归过程持续进行，称为一般条件。

2、所描述问题的最简单的情况，它是一个能控制递归过程结束的条件，称为基本条件。（递归出口）

递归的定义：

如果一个对象部分地由它自身组成或按它自己定义，则称它是递归的，所以说递归就是函数/过程/子过程在运行过程中直接或间接调用自身而产生的重入现象。

递归的基本思想：

就是把一个规模大的问题分为若干个规模较小的子问题求解，而每一个子问题又可以分为几个规模更小的子问题。基本上，所有的递归问题都可以用递推公式来表示。

最重要的一点就是假设子问题已经解决了，现在要基于已经解决的子问题来解决当前问题；或者说，必须先解决子问题，再基于子问题来解决当前问题或者可以这么理解：递归解决的是有依赖顺序关系的多个问题。

递归的优缺点：

优点：逻辑清楚，结构清晰，可读性好，代码简洁，效率高（拓展：DFS深度优先搜素，前中后序二叉树遍历）

缺点：函数调用开销大，空间复杂度高，有堆栈溢出的风险

非递归算法比较有哪些主要的优点和缺点

非递归算法和递归算法的主要优缺点：

非递归算法的优点：如果需要处理的数据规模比较大的时候，适合使用非递归算法。缺点：程序代码的可读性差一些。
递归算法的优点：程序代码的可读性要比非递归算法的好，如果需要处理的数据量比较小的时候，适合使用递归算法。缺点：当需要处理的数据规模比较大的时候，就不适合使用递归算法了。因为递归算法涉及到对堆栈的频繁操作（入栈、出栈），系统效率会很低，严重的时候会导致系统崩溃。

什么是递归递归有什么用

1、程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

2、递归一般的作用用于解决三类问题：
(1)数据的定义是按递归定义的。（Fibonacci函数）
(2)问题解法按递归算法实现。
这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。
(3)数据的结构形式是按递归定义的。

递归的通俗解释是什么

程序调用自身的编程技巧称为递归（ recursion）。递归作为一种算法在程序设计语言中广泛应用。 

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

递归的缺点：

递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

以上内容参考：百度百科-递归

C语言递归有什么用处，又有什么缺点

递归好处：代码更简洁清晰，可读性更好
递归可读性好这一点，对于初学者可能会反对。实际上递归的代码更清晰，但是从学习的角度要理解递归真正发生的什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。一般来说，一个人可能很容易的写出前中后序的二叉树遍历的递归算法，要写出相应的非递归算法就比较考验水平了，恐怕至少一半的人搞不定。所以说递归代码更简洁明了。

递归坏处：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。

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***(注意*代表空格，因为空格你看不到就不好表示).