递归:一个过程直接或间接的调用自己
注意:
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。
递归算法一般用于解决三类问题:
(1) 数据的定义是按递归定义的。(Fibonacci函数)
(2) 问题解法按递归算法实现。(回溯)
(3) 数据的结构形式是按递归定义的。(树的遍历,图的搜索)
递归的缺点:
递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
递归设计:
(1)对原问题S进行分析,假设出合理的叫嚣的问题S1;
(2)假设S1是可解的,再此基础上确定S的解,即给出S与S1的关系;
(3)确定一个特定的可解情况,作为递归的出口。
递归向非递归转换:
(1)直接转换法:可以直接求值,不需要回溯,使用中间变量来保存中间结果
(2)间接转换法:使用栈
来保存中间结果。
//阶乘,递归
public static int jiecheng(int n){
if(n > 1){
return jiecheng(n-1) * n;
}else{
return 1;
}
}
//阶乘,非递归
public static int jiecheng1(int n){
int s = 1;
for(int i = 1; i <=n; i++){
s = s*i;
}
return s;
}
//汉诺塔问题
public static void hanoi(int n, char a, char b, char c){
//结束条件,剩最后一个
if(n == 1){
//当剩最后一个时,将a上的盘移动到c上
move(a,1,c);
}else{
/*将n-1个从a移到b上,然后将最后一个移动到c上,
再以a为空柱,将b上的n-1个移动到c上
*/
hanoi(n-1,a,c,b);
move(a,n,c);
hanoi(n-1,b,a,c);
}
}
public static void move(char a, int n, char c){
System.out.println("从"+a+"移动到"+c);
}
分享到:
相关推荐
此程序是用来递归法写的, 可以实现求n的阶乘。
学习常用算法之(5)递归法
这个是用递归法来写最大公约数,当然原算法还是欧几里得算法;只不过代码比较简洁
解决汉诺塔问题, 用递归法将一个整数n转换成字符串。例如,如入483,应输出字符串“483”。N的位数不确定,可以是任意位整数。 1.3 建立一个包含加法函数、减法函数的动态链接库文件和一个包含加法函数、减法函数...
C语言递归法将整数转换为字符串
易语言递归法取排列组合例程源码,递归法取排列组合例程,子程序_取组合
递归法取排列组合易语言源码例程.rar 递归法取排列组合易语言源码例程.rar 递归法取排列组合易语言源码例程.rar 递归法取排列组合易语言源码例程.rar 递归法取排列组合易语言源码例程.rar 递归法取排列组合...
易语言源码递归法取排列组合易语言源码例程.rar 易语言源码递归法取排列组合易语言源码例程.rar 易语言源码递归法取排列组合易语言源码例程.rar 易语言源码递归法取排列组合易语言源码例程.rar 易语言源码递归法...
设计算法求解整数的划分问题,对给定的整数,输出划分数。并思考如何实现输出每个具体的划分。
本资源是数据结构中利用非递归法实现n皇后问题的一个C++代码,仅供参考,欢迎指正
迭代法、穷举搜索法、递推法、递归法、 贪婪法、回溯法、分治法、动态规划法
file文件中递归法可以方便删除软件做一些简单的操作
首先通过递归的方法实现二叉树的创建,分别访问左边子树和右边子树来实现先序、中序、后序的排列
Pospro写的一个Python程序:利用递归法和pygame实现迷宫寻路的动态展示
八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。这里提供一个C++语言的递归法的实现,代码已在VS2008下编译通过。相关博文地址: http://blog.csdn.net/jocodeoe/article/details/7067955
本资源是数据结构中利用递归法实现n皇后问题的一个C++代码,仅供参考,希望大家指正问题
C语言实现二叉树的前序、中序、后续遍历(递归法),大家可以看看哈。。。
用C语言编写的递归法素数分解程序,相信对大家有用。初学C的同学很适用,老师经常布置的题目哦
分形算法 递归法的研究 用于分型仿真软件代码
递归法实现:用递归法计算Fibonacci(斐波拉契)数列的第n项。