递归算法探究论文

A. 递归算法的介绍

递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).

B. 什么是递归算法

递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现像.

程序调用自身的编程技巧称为递归（ recursion）。
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。
一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
注意：
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口，否则将无限进行下去（死锁）。

递归算法一般用于解决三类问题：
(1)数据的定义是按递归定义的。(Fibonacci函数)
(2)问题解法按递归算法实现。(回溯)
(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)

递归的缺点：
递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

C. 递归算法的特性

递归算法两个特性
1.递归算法是一种分而治之，把复杂问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法的分析方法是有效地。
2递归算法的时间效率低

D. 请教高人 递归算法编写思路技巧

一个子程序（过程或函数）的定义中又直接或间接地调用该子程序本身，称为递归。递归是一种非常有用的程序设计方法。用递归算法编写的程序结构清晰，具有很好的可读性。递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
利用递归算法解题，首先要对问题的以下三个方面进行分析：
一、决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。
二、问题的边界条件及边界值。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。
三、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。把这些步骤或等式确定下来。
把以上三个方面分析好之后，就可以在子程序中定义递归调用。其一般格式为：
if 边界条件 1 成立 then
赋予边界值 1
【 elseif 边界条件 2 成立 then
赋予边界值 2
┇ 】
else
调用解决问题的通式
endif
例 1 ： 计算勒让德多项式的值

x 、 n 由键盘输入。
分析： 当 n ＝ 0 或 n ＝ 1 时，多项式的值都可以直接求出来，只是当 n ＞ 1 时，才使问题变得复杂，决定问题复杂程度的参数是 n 。根据题目提供的已知条件，我们也很容易发现，问题的边界条件及边界值有两个，分别是：当 n ＝ 0 时 P n (x) ＝ 1 和当 n ＝ 1 时 P n (x) ＝ x 。解决问题的通式是：
P n (x) ＝ ((2n － 1)P n － 1 (x) － (n － 1)P n － 2 (x)) ／ n 。
接下来按照上面介绍的一般格式定义递归子程序。
function Pnx(n as integer)
if n ＝ 0 then
Pnx ＝ 1
elseif n ＝ 1 then
Pnx ＝ x
else
Pnx ＝ ((2*n － 1)*Pnx(n － 1) － (n － 1)*Pnx(n － 2)) ／ n
endif
end function
例 2 ： Hanoi 塔问题：传说印度教的主神梵天创造世界时，在印度北部佛教圣地贝拿勒斯圣庙里，安放了一块黄铜板，板上插着三根宝石针，在其中一根宝石针上，自下而上地放着由大到小的 64 个金盘。这就是所谓的梵塔（ Hanoi ），如图。梵天要求僧侣们坚持不渝地按下面的规则把 64 个盘子移到另一根针上：

(1) 一次只能移一个盘子；
(2) 盘子只许在三根针上存放；
(3) 永远不许大盘压小盘。
梵天宣称，当把他创造世界之时所安放的 64 个盘子全部移到另一根针上时，世界将在一声霹雳声中毁灭。那时，他的虔诚的信徒都可以升天。
要求设计一个程序输出盘子的移动过程。
分析： 为了使问题更具有普遍性，设共有 n 个金盘，并且将金盘由小到大依次编号为 1 ， 2 ，…， n 。要把放在 s(source) 针上的 n 个金盘移到目的针 o(objective) 上，当只有一个金盘，即 n ＝ 1 时，问题是比较简单的，只要将编号为 1 的金盘从 s 针上直接移至 o 针上即可。可定义过程 move(s,1,o) 来实现。只是当 n>1 时，才使问题变得复杂。决定问题规模的参数是金盘的个数 n ；问题的边界条件及边界值是：当 n ＝ 1 时， move(s,1,o) 。
当金盘不止一个时，可以把最上面的 n － 1 个金盘看作一个整体。这样 n 个金盘就分成了两个部分：上面 n － 1 个金盘和最下面的编号为 n 的金盘。移动金盘的问题就可以分成下面三个子问题（三个步骤）：
(1) 借助 o 针，将 n － 1 个金盘（依照上述法则）从 s 针移至 i(indirect) 针上；
(2) 将编号为 n 的金盘直接从 s 针移至 o 针上；
(3) 借助 s 针，将 i 针上的 n － 1 个金盘（依照上述法则）移至 o 针上。如图

其中第二步只移动一个金盘，很容易解决。第一、第三步虽然不能直接解决，但我们已经把移动 n 个金盘的问题变成了移动 n － 1 个金盘的问题，问题的规模变小了。如果再把第一、第三步分别分成类似的三个子问题，移动 n － 1 个金盘的问题还可以变成移动 n － 2 个金盘的问题，同样可变成移动 n － 3 ，…， 1 个金盘的问题，从而将整个问题加以解决。
这三个步骤就是解决问题的通式，可以以过程的形式把它们定义下来：
hanoi(n － 1,s,o,i)
move(s,n,o)
hanoi(n － 1,i,s,o)
参考程序如下：
declare sub hanoi(n,s,i,o)
declare sub move(s,n,o)
input "How many disks?",n
s ＝ 1
i ＝ 2
o ＝ 3
call hanoi(n,s,i,o)
end
sub hanoi(n,s,i,o)
rem 递归子程序
if n ＝ 1 then
call move(s,1,o)
else
call hanoi(n － 1,s,o,i)
call move(s,n,o)
call hanoi(n － 1,i,s,o)
endif
end sub
sub move(s,n,o)
print "move disk";n;
print "from";s;"to";o
end sub

E. 递归算法有何特点

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

}

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

F. 关于《中序遍历二叉树的非递归算法》的论文

实用《数据结构》编程——二叉树的建立、中序遍历非递归C程序 宋丽敏 <正>近年来,伴随着计算机应用技术的快速发展,系统程序和应用程序的规模越来越大,应用领域越来越广泛.计算机的应用已不再局限于科学计算,而更多地应用于控制、管理及数据处理等非数值计算的处理工作.需要通过计算机加工、处理的数据对象也日益复杂化.《数据结构》课程就是一门以这些复杂的非数值型数据为研究对象,研【作者单位】：河北省廊坊职业技术学院(西校区) 065000【分类号】：G634.6【DOI】：cnki:ISSN:1005-9741.0.2004-02-009【正文快照】：近年来,伴随着计算机应用技术的快速发展,系统程序和应用程序的规模越来越大,应用领域越来越广泛.计算机的应用已不再局限于科学计算,而更多地应用于控制、管理及数据处理等非数值计算的处理工作.需要通过计算机加工、处理的数据对象也日益复杂化.《数据结构》课程就是一门以这 …… http://www.cnki.com.cn/Article/CJFDTotal-LKJX200402009.htm

G. 什么是递归算法

递归算法就是一个函数通过不断对自己的调用而求得最终结果的一种思维巧妙但是开销很大的算法。
比如：
汉诺塔的递归算法：
void move(char x,char y){
printf("%c-->%c\n",x,y);
}

void hanoi(int n,char one,char two,char three){
/*将n个盘从one座借助two座，移到three座*/
if(n==1) move(one,three);
else{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}

main(){
int n;
printf("input the number of diskes:");
scanf("%d",&n);
printf("The step to moving %3d diskes:\n",n);
hanoi(n,'A','B','C');
}
我说下递归的理解方法
首先：对于递归这一类函数，你不要纠结于他是干什么的，只要知道他的一个模糊功能是什么就行，等于把他想象成一个能实现某项功能的黑盒子，而不去管它的内部操作先，好，我们来看下汉诺塔是怎么样解决的
首先按我上面说的把递归函数想象成某个功能的黑盒子，void hanoi(int n,char one,char two,char three); 这个递归函数的功能是：能将n个由小到大放置的小长方形从one 位置，经过two位置 移动到three位置。那么你的主程序要解决的问题是要将m个的"汉诺块"由A借助B移动到C，根据我们上面说的汉诺塔的功能，我相信傻子也知道在主函数中写道：hanoi(m,A,B,C)就能实现将m个块由A借助B码放到C，对吧？所以，mian函数里面有hanoi(m,'A','C','B');这个调用。
接下来我们看看要实现hannoi的这个功能，hannoi函数应该干些什么？
在hannoi函数里有这么三行
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
同样以黑盒子的思想看待他，要想把n个块由A经过B搬到C去，是不是可以分为上面三步呢？
这三部是：第一步将除了最后最长的那一块以外的n-1块由one位置经由three搬到two 也就是从A由C搬到B 然后把最下面最长那一块用move函数把他从A直接搬到C 完事后 第三步再次将刚刚的n-1块借助hannoi函数的功能从B由A搬回到C 这样的三步实习了n块由A经过B到C这样一个功能，同样你不用纠结于hanoi函数到底如何实现这个功能的，只要知道他有这么一个神奇的功能就行
最后：递归都有收尾的时候对吧，收尾就是当只有一块的时候汉诺塔怎么个玩法呢？很简单吧，直接把那一块有Amove到C我们就完成了，所以hanoni这个函数最后还要加上 if(n==1)move(one,three);（当只有一块时，直接有Amove到C位置就行）这么一个条件就能实现hanoin函数n>=1时将n个块由A经由B搬到C的完整功能了。
递归这个复杂的思想就是这样简单解决的，呵呵 不知道你看懂没？纯手打，希望能帮你理解递归
总结起来就是不要管递归的具体实现细节步骤，只要知道他的功能是什么，然后利用他自己的功能通过调用他自己去解决自己的功能（好绕口啊，日）最后加上一个极限情况的条件即可，比如上面说的1个的情况。

H. 怎们理解递归算法

先不要往里想，越想越乱，先想好递归结束（最终返回）的条件，然后通过调用自己每次都将问题简化，这样说问题可能比较抽象，你看看数据结构书中关于树的部分，那里递归比较多，而且很多递归都不难，比如前序 中序 后序遍历，找些课本上的程序，用一些简单的树为例子一步步走一下，相信你会更清晰的

I. 编写一个递归算法计算并返回一个链表的长度

如果是不带头结点的:

public int length(LNode ln){
if(ln==null){
return 0;
}
return 1+length(ln.getNext());
}

J. 用递归算法解决问题

递归函数通常用来解决结构自相似的问题。所谓结构自相似，是指构成原问题的子问题与原问题在结构上相似，可以用类似的方法解决。具体地，整个问题的解决，可以分为两部分：第一部分是一些特殊情况，有直接的解法；第二部分与原问题相似，但比原问题的规模小。实际上，递归是把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的问题，直至每个小问题都可以直接解决。因此，递归有两个基本要素：
（1）边界条件：确定递归到何时终止，也称为递归出口。
（2）递归模式：大问题是如何分解为小问题的，也称为递归体。递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
递归就是某个函数直接或间接地调用了自身，这种调用方式叫做递归调用。说白了，还是函数调用。既然是函数调用，那么就有一个雷打不动的原则：所有被调用的函数都将创建一个副本，各自为调用者服务，而不受其他函数的影响。