递归算法缺点

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

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

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

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

递归的定义：

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

递归的基本思想：

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

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

递归的优缺点：

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

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

Ⅱ 递归有什么坏处

递归。要正推到已知条件，然后再从已经条件一步步返回。
如果量大的时候，太浪费存储空间。
换句话也就是时间复杂度太大了。

Ⅲ 递归算法的低效性

先回答问题。
内存方面，一般情况下递归的开销比非递归大；
运行速度方面，一般情况下递归比非递归快；
代码实现上，难度不一而论，要看具体问题上人脑解决和电脑解决的思路差异大小，一般而言，递归问题用非递归思路和普通问题用递归思路时代码实现都将复杂化；
运行稳定性上，非递归明显占优；
代码量，永远是递归最少；

单论递归算法的低效性，一般指的是其内存开销太大。其他的特性与非递归比没有确定的结果，要试解决的问题而定。

这里有一篇非常之精辟的短文，想要深入了解递归可以看下。
http://hi..com/ninke/blog/item/e3e244a942b621fd1f17a25e.html

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

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

Ⅳ 递归的主要用途和好处是什么精髓在哪儿

这里有:
递归 递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现像.
程序调用自身的编程技巧称为递归（ recursion）。
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。
一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
注意：
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
递归算法一般用于解决三类问题：
(1)数据的定义是按递归定义的。(Fibonacci函数)
(2)问题解法按递归算法实现。(回溯)
(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)
递归的缺点：
递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等

Ⅵ 递归的通俗解释是什么

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

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

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

递归的缺点：

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

以上内容参考：网络-递归

Ⅶ 递归算法有何特点

递归4—递归的弱点

之所以没有把这段归为算法的讨论，因为这里讨论的不在是算法，而只是讨论一下滥用递归的不好的一面。

递归的用法似乎是很容易的，但是递归还是有她的致命弱点，那就是如果运用不恰当，滥用递归，程序的运行效率会非常的低，低到什么程度，低到出乎你的想象！当然，平时的小程序是看不出什么的，但是一旦在大项目里滥用递归，效率问题将引起程序的实用性的大大降低！

例子：求1到200的自然数的和。

第一种做法：

#include <stdio.h>

void main()

{

int i;

int sum=0;

for(i=1;i<=200;i++)

{

sum+=i;

}

printf("%d\n",sum);

}

该代码中使用变量2个，计算200次。再看下个代码：

#include <stdio.h>

int add(int i)

{

if(i==1)

{

return i;

}

else

{

return i+add(i-1);

}

}

void main()

{

int i;

int sum=0;

sum=add(200);

printf("%d\n",sum);

}

但看add（）函数，每次调用要声明一个变量，每次调用要计算一次，所以应该是200个变量，200次计算，对比一下想想，如果程序要求递归次数非常多的时候，而且类似与这种情况，我们还能用递归去做吗？这个时候宁愿麻烦点去考虑其他办法，也要尝试摆脱递归的干扰。

21:21 | 添加评论 | 固定链接 | 引用通告 (0) | 记录它 | 计算机与 Internet
程序算法5—递归3—递归的再次挖掘

递归的魅力就在于递归的代码，写出来实在是太简练了，而且能解决很多看起来似乎有规律但是又不是一下子能表达清楚的一些问题。思路清晰了，递归一写出来问题立即就解决了，给人一重感觉，递归这么好用。我们在此再更深的挖掘一下递归的用法。

之前再强调一点，也许有人会问，你前边的例子用递归似乎是更麻烦了。是，是麻烦了，因为为了方便理解，只能举一些容易理解的例子，一般等实际应用递归的时候，远远不是这种状态。

好了我们现在看一个数字的序列；有一组数的集合{1，2，4，7，11，16，22，29，37，46，56……}我故意多给几项，一般是只给前4项让你找规律的。序列给了，要求是求前50项的和。规律？有？还是没有？一看就象有，但是又看不出来，我多给了几项，应该很快看出来了，哦，原来每相邻的两项的差是个自然数排列，2-1=1，4-2=2，7-4=3，11-7=4，16-11=5……

好了，把规律找出来了，一开始可能觉得没头绪，没问题，咱们把这个序列存放到一个数组总可以吧！那我们就声明一个数组，存放前50个数据，一个一个相加总可以了。于是有了下边的写法：

#include <stdio.h>

void main()

{

int i,a[50],sum=0;

a[0]=1;

for(i=1;i<50;i++)

{

a[i]=a[i-1]+i;

}

for(i=0;i<50;i++)

{

sum+=a[i];

}

printf("%d\n",sum);

}

好了，代码运行一下，结果出来了，正确不正确呢？自己测试吧，把50项改成1、2、3、4、5……项，试试前多少项是不是正确，虽然这不是正确的测试方法，但是的确是常用的测试方法。

等到这个代码已经完全理解了，完全明白了正个计算过程，我们就应该对这段代码进行改写优化了，毕竟这个代码还是不值得用一个数组的，那么我们尝试着只用变量去做一下：

#include <stdio.h>

void main()

{

int i;

int number=1;

int sum=0;

for(i=0;i<50;i++)

{

number+=i;

sum+=number;

}

printf("%d\n",sum);

}

不知道我这样写是不是跨度大了点，但是我不准备详细解释了，很多东西需要你去认真分析的，所以很多东西如果不懂，自己想清楚比别人解释的效果会更好，因为别人讲只能让你理解，如果你自己去想，你就在理解的同时学会了思考。

这个代码写出来，不要继续看下去，先自己尝试着把这个题目用递归做一下看看自己能不能写出来，当然，递归并不是那么轻松就能使用的，有时候也是需要去细心设计的。如果做出来了，对比一下下边的代码，如果没有写出来，建议认真分析后边的代码，然后最好是能完全掌握，能自己随时把这行代码写出来：

#include <stdio.h>

int add(int n,int num,int i)

{

num+=i;

if(i>=n-1)

{

return num;

}

else

{

return num+add(n,num,i+1);

}

}

void main()

{

int sum;

sum=add(50,1,0); /*50表示前50象项*/

printf("%d\n",sum);

}

当然这个代码中的n只是一个参考变量，如果把if(i>=n-1)中的n该成50，那么就不需要这个n了，函数两个参数就可以了，这样写是为了修改方便。

20:28 | 添加评论 | 固定链接 | 引用通告 (0) | 记录它 | 计算机与 Internet
程序算法4—递归2—递归的魅力

两天没有再写下去，因为毕竟有时候会有点心情问题，有时候觉得心情不好，一下子什么东西都想不起来了，很多时候写一些东西是需要状态的，一旦状态有了，想的东西才能顺利的写出来，虽然有些东西写出来在别人看来很垃圾，但是起码自己觉得还是相当满意的，我写这个本来就没有多少技术含量，只是想给初学程序的人一些指引，加快他们对程序的领悟！

好了，言归正传，继续上次递归的讨论，看看递归的魅力所在。

有这样一个问题，说一个猴子和一堆苹果，猴子一天吃一半，然后再吃一个，10天后剩下一个了，也就是说吃了10次，剩下1个了。问原来一共有多少苹果。

当然我们的目的不是求出苹果的数量，而是寻求一种解决问题的方法，这个问题一出来，通常对程序掌握深度不一样的朋友对这个题会有不同的认识，首先介绍一种解决方法，这种人脑袋还是比较聪明的，思路非常的明确，也有可能语言工具掌握的也不错，代码写出来非常准确，先看一下代码再做评价吧：

#include <stdio.h>

void main()

{

int day=10;

int apple;

int i,j;

for(i=1;;i++)

{

apple=i;

for(j=0;j<day;j++)

{

if(apple%2==0&&apple>0)

{

apple/=2;

apple--;

}

else

{

break;

}

}

if(j==day&&apple==1)

{

printf("%d\n",i);

return;

}

}

}

程序的大概思路很明确，简单介绍一下，这种写法就是从一个苹果开始算起，for(i=1;;i++)的作用就是改变苹果的数量，如果1个符合条件，那就试试2个，然后3个、4个一直到适合为止，里边的for循环就是把每一次取得的苹果的数目进行计算，如果每次都能顺利的被2整除（也就是说每次都能保证猴子能正好吃一半），然后再减一一直到最后，如果最后苹果剩下是一个而且天数正好是10天，那么就输出一下苹果的数目，整个程序退出，如果看不明白的没关系，这个写法非常的不适用，我们叫写出这种算法的人傻X，虽然这种人脑袋也挺聪明，能写出一些新鲜的写法，但是又脏又臭，代码既不简练又不高效。

所以说，有时候有些人以为自己学的很好了，自己所做的一切都是最好的，这种想法是不正确的，也许有些初学者没有什么经验写出来的代码却更让人容易明白点，那么也是先看看代码：

#include <stdio.h>

void main()

{

int day[11];

int i;

day[0]=1;

for(i=1;i<11;i++)

{

day[i]=(day[i-1]+1)*2;

}

printf("%d\n",day[10]);

}

代码不长，而且也恰当的应用了题目中的规律，不是说要吃一半然后再吃一个吗？那我用数组来存放每天苹果的数量，用day[0]表示最后一天的苹果数量，那就是剩下的一个，然后就是找规律了，什么规律？就是如果猴子不多吃一个的话，那就是正好吃了一半，也就是说猴子当天吃了之后剩余的苹果的数目加1个然后再乘以2就是前一天的数目了，这样一想这个题目就简单的多了，于是这个题用数组就轻松的做出来了。

那么这个代码究竟是不是已经很好了呢，我们注意到，这里边每个数组元素只用了一次并没有被重复使用，再这种情况下我们是不是可以用一种方法代替数组呢？于是就有了更优化的写法，这个写法似乎已经是相当简练了：

#include <stdio.h>

void main()

{

int apple=1;

int i;

for(i=0;i<10;i++)

{

apple=(apple+1)*2;

}

printf("%d\n",apple);

}

代码写到这里已经把问题完全抽象化了，所以我们就应该站在数学的角度去分析了。也许我们就应该结束了讨论，但是偏偏这个时候，又来了递归，悄悄的通过美丽的调用显示了一下她的魅力：

#include <stdio.h>

int apple(int i)

{

if(i==0)

{

return 1;

}

else

{

return (apple(i-1)+1)*2;

}

}

void main()

{

int i;

i=apple(10);

printf("%d\n",i);

}

原理都还是一样的，但是写出来的格式已经完全变掉了，没有了for循环。假想一个复杂的问题远比这个问题复杂，而且没有固定循环次数，那么我们再使用循环虽然也能解决问题，但是可能面临循环难以设计、控制等问题，这个时候用递归可能就会让问题变的非常的清晰。

另外说一点，一般我这里的代码，并不是从最差到最好的，基本排列是从最差到最合适的代码（当然是本人认为最合适的，也许还有更好的，本人能力所限了），然后最后给出一种比较违反常规的代码，一般是不赞成用最后一种代码的，当然有时候最后一种代码也许是最好的选择，看情况吧！

20:25 | 添加评论 | 固定链接 | 引用通告 (0) | 记录它 | 计算机与 Internet
10月15日
程序算法3—递归1—递归小显威力

现在用C语言实现一个字符串的倒序输出，当然，方法也是很多的，但是如果程序中能有相对优化的方法或者简单明了易读的方法，那对你自己或者别人都是一种幸福。

第一种写法，这类写法既浪费内存又不实用，一般是刚学程序的才这样做，程序的结构很简单，利用的是数组：

#include <stdio.h>

void main()

{

char c[2000];

int i,length=0;

for(i=0;i<2000;i++)

{

scanf("%c",&c[i]);

if(c[i]=='\n')

{

break;

}

else

{

length++;

}

}

for(i=length;i>0;i--)

{

printf("%c",c[i-1]);

}

printf("\n");

}

这段代码中的数组，声明大了浪费内存空间，声明小了又怕不够，所以写这种代码的人一般写完之后会祈祷，祈祷测试的人不要输入的太多，太多就不能完全显示了！

与其这么提心吊胆，于是又有人想出了第二种方法，终于解决了一些问题，而且完全实现了程序的实际要求，于是，这种人经过一番苦想，觉得问题终于可以解决了，这种方法看起来是一种很不错的方法。

#include <stdio.h>

#include <malloc.h>

void main()

{

int i;

char *c;

c=(char *)malloc(1*sizeof(char));

for(i=0;;i++)

{

*(c+i)=getchar();

if(*(c+i)=='\n')

{

*(c+i)='\0';

break;

}

else

c=(char *)realloc(c,(i+2)*sizeof(char));

}

for(--i;i>=0;i--)

{

putchar(*(c+i));

}

printf("\n");

free(c);

}

怎么样？不错，准确的应用内存，几乎没有浪费什么空间，这种方法也体现了一下指针的强大功能，写这个程序虽然不敢说这个人已经掌握了指针的应用，但是起码可以说他已经会用指针了。代码写出来，看起来已经有点美感。

但是也有一些人还是比较喜欢动脑筋的，经过一番思考，终于想出了第三种比较容易写的方法，也许有写初学者可能觉得有些难度，但是事实上这个东西一点都不难，如果稍微有点程序功底之后再看这段代码，应该是相当轻松！

#include <stdio.h>

void run()

{

char c;

c=getchar();

if(c!='\n')

{

run();

}

else

{

return;

}

putchar(c);

}

void main()

{

run();

printf("\n");

}

写出的代码让人眼前一亮，哇！原来递归功能简单而又好用，那我们为什么不好好利用呢？但是递归也不一定就是最好的选择，因为有时候虽然递归用起来很方便，但是效率却不高，以后的讨论中还会详细说明。

Ⅷ 在c语言中递归和迭代有什么区别和联系各自的优缺点是什么二者分别适合解决什

能力有限，仅知几点
两者都是重复某一操作直到满足条件为止。
不同之处在于，递归是函数调用自身，而迭代是使用循环。
某些情况下递归更加简单，可读性更高，而用循环则十分复杂。如二分法，快速排序等。
递归很容易导致栈溢出，导致程序崩溃，而循环不会。
综上所述，能用循环用循环，递归是万不得已的手段。

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

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

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