首页 > 代码库 > 递归算法
递归算法
递归
刚刚上机回来，做的是对二叉树的递归算法，因此想将关于递归做一个总结。
递归，从字面意思来看，是传递归回原来有的（我理解的），百度给出的意思是：按照某一包含有限步数的法则或公式对一个或多个前面的元素进行运算、以确定一系列元素(如数或函数)的方法。百度给出的定义感觉好高大上，总的来看，递归的步骤有限的，同时，它有个不断循环的递归体，既然是有限的，那么它必定有个限制，让它停下来，这个也就是所说的递归出口。递归思想是非常重要的。
原谅我的表达无力，还是通过一个小例子来见识下这重要的递归思想。
1：求10！
分析：10！=10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
9！=9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
8!= 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
……
……
那么可以得出 10！=10*（9！）
9！=9*（8！）
……
是否可以看到规律：一个数的阶乘都可以写成这个数乘以这个数减一的阶乘。即 n!=n*(n-1)! （递归体） 就简简对这个式子来看 它是不是应该有个限制，否则1！=1*（-1）这显然不对啊，同时可以得出当写到1！时应当停下来，即1！=1（递归出口）；
用代码来表达下：
int fun(int n)
{
int f=1;
if(n==1)
n=1;
else
f=n*fun(n-1);
return f;
}
对于这道题来说，重要的在于自己调用自己，是递归思想中重要的角色，代码写出来了，现在来运行下程序，首先，给n一个值 即10，
进入到fun这个函数体中，判断10是否等于一，不等于，执行else，
f=10*fun（n-1）；（这里就是自己调用自己），然后计算fun（n-1），
对于现在这个fun函数体来说 n就是n-1了，即9，判断9是否等于一，不等于，执行else，f=9*fun(8)；…… 直到n=1，这时候，判断1是否等于一，等于，则n=1；那么fun（1）=1，所以fun（2）=2*fun（1）=2，fun（3）=3*fun（2）=6 ……
综上：完整代码如下：
#include <stdio.h>
int fun(int n)
{
int f=1;
if(n==1)
n=1;
else
f=n*fun(n-1);
return f;
}
int main(void)
{ printf("the result is : %d",fun(10));
return 0;
}
运行结果为：3628800
这道题，是递归思想的最好的体现，简单好理解。
下面这个例子是递归中的经典，汉诺塔问题：
汉诺(hanoi)塔传说:
在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的６４片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽
现在来分析：只有一个盘子时：
如图：
直接将A上的盘子移到c盘上，即a->c b此时没有发挥作用。
有两个盘子时：
即 A->B,A->C,B->C
多画几次就会发现，A上的盘子总是要借助B这个来移到c盘上，
下面看下这个转换成代码的过程：n表示盘子数 可以分为三个步骤：
1：将A盘上的n-1个盘片借助C盘移到B盘。
2：把第n个盘从A盘移到c上。
3：再把b上的n-1个盘片借助A盘移到c盘。
代码如下： //hanoi tower
#include <stdio.h>
void fun(int i,char a,char b,char c)
{
if(i==1)
printf("%c to %c\n",a,c); //当有一个盘子时，将A盘移到C盘
else
{ fun(i-1,a,c,b); //余下的i-1,借助c盘移到b盘；
printf("%c to %c\n",a,c);
fun(i-1,b,a,c); //余下的，借助a盘移到c盘
}
}
int main(void)
{
int i;//表示圆盘的数量
printf("please input the plate‘number:");
scanf("%d",&i);
fun(i,‘A‘,‘B‘,‘C‘);
return 0;
}
运行结果：
通过这两个例子，可以知道，对于题的理解是特别重要的，这里的自己调用自己，一定要好好理解。
下面来说下递归的优点和缺点：
用到递归，会发现代码量会大量的减少，只需少量的程序就可描述出解题过程所需要的多次重复计算，结构清晰，易读，
但是，递归会导致运行效率低，不断地自己调用自己，耗费时间，占用空间（与非递归来相比），且容易溢出（这是一个潜在的隐患）。
递归的思想还用在树的使用上：
例如二叉树：
typedef struct Node
{
char Date;
struct Node *Lchild;
struct Node *Rchild;
}BiNode,*BiTree;
首先是二叉树的建立：
void CreatTree( BiTree *root) ////创建二叉树
{ ////
char f; ////
f=getchar(); ////
if(f==‘^‘) ////
*root=NULL; ////
else ////
{ ////
*root=(BiTree)malloc(sizeof(BiNode)); ////
(*root)->Date=f; ////
CreatTree(&((*root)->Lchild));
CreatTree(&((*root)->Rchild)); }
}
这里在介绍下先序遍历二叉树：
void PreOrder(BiTree root) //// 先序遍历
{ ////
if(root) ////
{ ////
Visit(root->Date); ////访问根节点
PreOrder(root->Lchild); ////
PreOrder(root->Rchild); ////
} ////
}
递归的思想在二叉树上得到了充分的体现，因为其可读性强，因此有人会说小程序用循环，大程序用递归（但是递归的缺点也在那里摆着，酌情使用）。
By ：暖暖
2014.11.10
递归算法