递归算法

㈠ 什么是递归算法

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

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

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

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

㈡ 什么是递归算法有什么作用

作者名：不详 来源：网友提供 05年7月7日

无法贴图 ，自己到 http://51zk.csai.cn/sjjg/NO00223.htm 看去吧

1、调用子程序的含义：
在过程和函数的学习中，我们知道调用子程序的一般形式是：主程序调用子程序A，子程序A调用子程序B，如图如示，这个过程实际上是：

＠当主程序执行到调用子程序A语句时，系统保存一些必要的现场数据，然后执行类似于BASIC语言的GOTO语句，跳转到子程序A（为了说得简单些，我这里忽略了参数传递这个过程）。
＠当子程序A执行到调用子程序B语句时，系统作法如上，跳转到子程序B。
＠子程序B执行完所有语句后，跳转回子程序A调用子程序B语句的下一条语句（我这又忽略了返回值处理）
＠子程序A执行完后，跳转回主程序调用子程序A语句的下一条语句
＠主程序执行到结束。
做个比较：我在吃饭（执行主程序）吃到一半时，某人叫我（执行子程序A），话正说到一半，电话又响了起来（执行子程序B），我只要先接完电话，再和某人把话说完，最后把饭吃完（我这饭吃得也够累的了J）。
2、认识递归函数
我们在高中时都学过数学归纳法，例：
求 n！
我们可以把n！这么定义

也就是说要求3！，我们必须先求出2！，要求2！，必须先求1！，要求1！，就必须先求0！，而0!=1，所以1!=0!*1=1，再进而求2!，3!。分别用函数表示，则如图：

我们可以观察到，除计算0！子程序外，其他的子程序基本相似，我们可以设计这么一个子程序：
int factorial(int i){
int res;
res=factorial(I-1)*i;
return res;
}
那么当执行主程序语句s=factorial(3)时，就会执行factorial(3),但在执行factorial(3)，又会调用factorial(2)，这时大家要注意，factorial(3)和factorial(2)虽然是同一个代码段，但在内存中它的数据区是两份！而执行factorial(2)时又会调用factorial（1），执行factorial（1）时又会调用factorial（0），每调用一次factorial函数，它就会在内存中新增一个数据区，那么这些复制了多份的函数大家可以把它看成是多个不同名的函数来理解；
但我们这个函数有点问题，在执行factorial（0）时，它又会调用factorial（－1）。。。造成死循环，也就是说，在factorial函数中，我们要在适当的时候保证不再调用该函数，也就是不执行res=factorial(I-1)*i;这条调用语句。所以函数要改成：
int factorial(int i){
int res;
if (I>0) res=factorial(I-1)*i; else res=1;
return res;
}
那么求3!的实际执行过程如图所示：

3、如何考虑用递归的方法来解决问题
例：求s=1+2+3+4+5+6+……+n
本来这个问题我们过去常用循环累加的方法。而这里如要用递归的方法，必须考虑两点：
1） 能否把问题转化成递归形式的描述；
2） 是否有递归结束的边界条件。
设:函数s(n)=1+2+3+…+(n-1)+n
显然递归的两个条件都有了：
1） s(n) =s(n-1)+n
2） s(1)=1
所以源程序为：
int progression(int n){
int res;
if (n=1 )res=1 else res=progression(n-1)+n;
return res;
}
4、递归的应用
中序遍历二叉树
void inorder (BinTree T){
if (T){
inorder(T->lchild);
printf(“%c”,T->data);
inorder(T->rchild);
}
}
现假设树如图（为了讲解方便，树很简单）

＠执行第一次调用inorder1，T指向顶结点，T不为空，所以第二次调用inorder2；
＠T指向顶结点的左子树结点也就是B，不为空，所以第三次调用inorder3；
＠T指向B结点的左子树结点，为空，所以什么都不执行，返回inorder2；
＠打印B结点的DATA域值“b”；
＠第四次调用inorder4，去访问B子树的右结点
＠T指向B结点的右子树结点，为空，所以什么都不执行，返回inorder2；
＠返回inorder1；
＠打印A结点的DATA域值“a”；
＠第五次调用inorder5，去访问A子树的右结点；
＠T指向A结点的右子树结点，为空，所以什么都不执行，返回inorder1；
＠inorder1执行完毕，返回。

㈢ 求阶乘n!的递归算法

#include<stdio.h>
int fun(int n)
{
if(n==1||n==0) return 1;//如果参数是0或者1返回1
return n*fun(n-1);//否则返回n和下次递归的积
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",fun(n));
return 0;
}
/*
5
120
*/

【递归算法的原理】

递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写
递归能使程序变得简洁和清晰。

㈣ 递归算法

0+1 =1
1+1 =2
1+2 =3
2+3 = 5
3+5 =8
.....
an = a(n-1)+a(n-2)
sn = a1+a2+....+an=......
时间有限后面的自己够定吧

㈤ 快排 递归算法

procere qsort(i,j:longint);
var r,l:longint;mid,temp:longint;
begin
r:=j;
l:=i;
mid:=a[r];
repeat
while a[r]>mid do dec(r);
while a[l]<mid do inc(l);
if r>=l
then
begin
temp:=a[r];
a[r]:=a[l];
a[l]:=temp;
inc(l);dec(r);
end;
until r<l;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
//A是排序数组
//基本方法:把小于MIN的放在一边,
把大于MIN的放在另一边. 递归解决.时间复杂度o(n*log(n))

㈥ C语言递归算法

int f(int n)
{
if (n>0)
{
return n*f(n/2);
}
else if(n==0)
{
return n+1;
}
}

㈦ 递归算法是什么

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。

㈧ 树的递归算法

答案是正确的啊。
if(root)就是如果root!=0，这里root是一个指针，指向结构体struct node的指针，第一次进入函数它就是指向根节点A的指针
运行步骤：
如果指向A的指针不为空(不为0),打印'A',
递归调用函数指向A的左孩子节点
如果指向B的指针不为空(不为0),打印'B',
递归调用函数指向B的左孩子节点
如果指向C的指针不为空(不为0),打印'C',
递归调用函数指向C的左孩子节点
由于C的左孩子节点为空，所以本次递归traversal(root->lchild)结束，回到上一层递归中即从C的左孩子节点回到C中，然后执行traversal(root->lchild)这一句下面一句，打印出'C'
然后递归调用traversal(root->rchild);指向C的右孩子节点
如果指向E的指针不为空(不为0),打印'E',
然后再递归指向E的左孩子节点，为空再返回到E中，再次打印出'E',然后再指向E的右孩子节点，为空，E的递归结束返回上一层递归即C中，然后C也到达末尾结束返回上一层递归B中，然后执行traversal(root->lchild)这一句下面一句，打印出'B'
然后递归调用traversal(root->rchild);指向B的右孩子节点
......
如此不断进入某个节点的子节点操作后再从子节点返回父节点，层层进入再层层向上返回，从而遍历树中各个节点，最终得出结果：
A B C C E E B A D F F D G 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个的情况。

㈩ 简单的递归算法

我不明白什么是对对象依赖太大。这个全用static，不存在对象：）
public class DrawStar {
public static void main(String[] args) {
drawStar(5);
}

private static void drawStar(int n) {
if (n > 0) {
drawLine(n);
drawStar(n - 1);
drawLine(n);
}
}

private static void drawLine(int n) {
for (int i = 0; i < n; i++)
System.out.print("*");
System.out.println();
}
}