递归算法有何特点

自身调用自身,结构简洁明了,使程序更加易读,缺点是耗费了额外的空间时间.

这个的解释不是很好说明，其实就是循环调用的一种，
在定义的函数中再调用这个函数进行循环．

这个~~`~~
特点就是它很递归
建议你去看书吧
。。

递归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");

}

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