Java实现简单的递归操作[通俗易懂]
大家好,又见面了,我是你们的朋友全栈君。
在数据结构算法设计中,或者一个方法的具体实现的时候,有一种方法叫做“递归”,这种方法在思想上并不是特别难,但是实现起来还是有一些需要注意的。虽然对于很多递归算法都可以由相应的循环迭代来代替,但是对于一些比较抽象复杂的算法不用递归很难理解与实现。 递归分为直接递归和间接递归,就简单分享一下两个小的直接递归。 对于递归的概念,其实你可以简单的理解为自己定义自己,记得小时候看过一部电视剧《狼毒花》,里面主角叫做“常发”,但是个文盲,老师问他叫什么,他说“常发”。“哪个常?”“常发的常啊!”“哪个发?”“常发的发啊!”结果第二节课老师就让一群小朋友一起喊“常发的常,常发的发,傻瓜的傻,傻瓜的瓜”。言归正传,显然在多数情况下递归是解释一个想法或者定义的一种合理方法。在思想上递归类似于数学中曾经学过的数学归纳法。 递归的实现: 递归的实现要注意有两点:一个递归的选项和一个非递归的选项,后者成为基础情形(base case)。基础情形是递归的终结情形,没有基础情形或者处理不好都会导致无穷递归,这是我们不想要的结果。递归实现起来最关键的是处理好基础情形。 结合具体事例在说一下递归回溯的过程。 下边来写两个小程序: 1、爬楼梯算法:已知一个楼梯有n个台阶,每次可以选择迈上一个或者两个台阶,求走完一共有多少种不同的走法。 方法如下:
递归函数有返回值的比没有返回值的麻烦一点,因为一个函数只有一个返回值,但是递归还要求有基础情形的存在,所以还必须有if判断来终止递归。所以在每一个if或者else后边都有一个return,这样保证函数在任何一种情况下都有且仅有一个返回值。 分析一下这个算法: A:如果有0个台阶,那么有0种走法,这个不用多说; B:如果有1个台阶,那么有1种走法; C:如果有2个台阶,那么有2种走法(一次走1个,走两次;一次走两个); 以上的B和C就是基础情形。 D:接下来就是递归了,如果台阶数目多于2个,那么首先第一步就有两种选择:第一次走1个,或者第一次走两个。这样除了第一次后边的走法就有了两种情形:climbStairs(n-1)和climbStairs(n-2)。这样一直递归下去,直到出现到了基础情形(即n=1或n=2的情形),递归到这个地方(基础情形),然后开始回溯 ,这就是所说的和递归密切相关的“回溯”了。回溯,顾名思义就是从结果倒着回去,找到整个过程,进而分析这个路径或者说是实现的过程。
需要注意的是,这个算法实现思路上简单,但是复杂度并没有降低,还牵扯回溯保存堆栈问题(其实递归的设计尽量避免这种嵌套两个的递归方式(climb(n)中包含climb(n-1)和climb(n-2)),这种操作会使得堆栈开辟空间随着n的增大以指数型增长,最终程序很容易崩溃),而且在台阶数目多到一定数量的时候会越界(走法次数会超出int的范围),所以递归程序很大程度上就是思想实现设计上简单理解一些。 下边是源代码:
package leetcode;
public class ClimbStairs {
// **************************************************************
public int climbStairs(int n) {
int i=1;
if(n<=0)
return 0;
if(n==1){
return i;
}
if(n==2){
i++;
return i;
}
else
return climbStairs(n-1)+climbStairs(n-2);
}
//**************************************************************
public static void main(String []args){
ClimbStairs cs=new ClimbStairs();
int a =cs.climbStairs(4);
System.out.println(a);
}
}
然后还有几个比较典型的递归问题:比如说迷宫问题,或者最经典的汉诺塔问题,下边都给出源码,大家一块儿学习一下。
汉诺塔问题:一次只能移动一个盘子;不能把大盘子放在小盘子上;除去盘子在两个柱子之间移动的瞬间,盘子必须都在柱子上。(在这三点要求下把盘子从起始柱子A全部移动到目标柱子C上)
代码如下: 基础情形:n==1的时候终止递归,进行回溯。
public class HanNuoTower {
public void tower(int n,char s,char m,char e)//n个塔从s经过m最终全部移动到e
{
if(n==1)
move(s,e);
else
{
tower(n-1,s,e,m);
move(s,e);
tower(n-1,m,s,e);
}
}
public void move(char s,char e){
System.out.println("move "+s+" to "+e);
}
public static void main(String []args){
HanNuoTower hnt =new HanNuoTower();
hnt.tower(4,'A','B','C');
}
}
迷宫走法:二维数组构成一个迷宫,1表示通路,0表示不通,找到一条路径从起始点(traverse函数的参数)到终点(右下角点)。
基础情形:row=grid.length-1&&column=grid[0].length-1时done=true;
public class Maze {
private final int TRIED=3;
private final int PATH=7;
private int [][] grid={ {1,1,1,0,0,1,0,1,0,0},
{0,0,1,1,1,0,0,0,0,0},
{1,0,1,0,0,0,1,1,1,1},
{1,1,1,1,1,0,0,0,1,1},
{0,0,0,0,1,1,1,0,0,0},
{1,0,1,0,1,0,0,1,0,0},
{1,0,0,1,1,1,1,1,1,1} };
public boolean traverse(int row,int column){
boolean done =false;
if(valid(row,column))
{
grid[row][column]=TRIED;
if(row==grid.length-1&&column==grid[0].length-1)
done=true;
else
{
done=traverse(row+1,column);//down
if(!done)
done=traverse(row,column+1);//right
if(!done)
done=traverse(row-1,column);//up
if(!done)
done=traverse(row,column-1);//left
}
if(done)
grid[row][column]=PATH;
}
return done;
}
private boolean valid(int row,int column){
boolean result=false;
if(row>=0&&row<grid.length&&column>=0&&column<grid[row].length)
if(grid[row][column]==1)
result=true;
return result;
}
public String toString(){
String result="\n";
for (int row=0;row<grid.length;row++){
for(int column=0;column<grid[row].length;column++){
result +=grid[row][column]+" ";
}
result+="\n";
}
return result;
}
public static void main (String []args){
Maze maze=new Maze();
System.out.println(maze);
if(maze.traverse(0, 0))
System.out.println("The maze was successfully travelled!");
else
System.out.println("There is no possible path.");
System.out.println(maze);
}
}
还有一个九连环的操作,有兴趣的话可以一起看看。Java递归解决九连环问题 如有不得当之处,还望诸位大神指教!
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/192035.html原文链接:https://javaforall.cn
相关文章
- Java设置全局变量_java如何定义全局变量
- java局域网发送文件_Java如何实现局域网文件传输代码案例分享
- Java连接MySQL mysql-connector-java-bin.jar驱动包的下载与安装
- java 删除目录下所有文件_Java删除文件、目录及目录下所有文件的方法实例
- java random函数用法_JAVA的Random类的用法详解[通俗易懂]
- java后端开发需要什么_从事Java后端开发,要学习哪些知识和技能?[通俗易懂]
- java工作流_Java 实现简单工作流
- java axis_Java 使用Axis实现WebService实例
- java中random方法取值范围_Java Random.nextInt()方法,随机产生某个范围内的整数
- native2ascii java_Native2Ascii和Ascii2Native的Java实现
- java的栈内存和堆内存_Java本地方法栈
- java socket详解_Java Socket 编程原理及教程「建议收藏」
- Java递归 通过递归实现累加
- Java最新简答题
- Java学习笔记之三java中的变量和常量详解编程语言
- eeOracle放弃Java EE:梦想的终结(oracle放弃java)
- Linux下Java开发:给初学者的指引(linux下java编程)
- 实现Linux上的Java环境:从安装到配置(linux安装java环境)
- 实现使用Java实现Redis消息队列(redis消息队列java)
- Java调试Linux:探索新的技术可能性(java调试Linux)
- Java轻松使用Redis实现数据高效存储(java使用redis)
- Java连接SQL Server:实现数据库完美对接(java链接sqlserver)
- Java调用Redis实现高性能数据存储(java调用redis)
- Linux环境中如何顺利执行Java程序?(linux下执行java)
- 使用Java连接SQL Server数据库,轻松实现数据交互(java连sqlserver)
- Linux系统中下载Java的方法(linux下java下载)
- 在Linux上实现Java程序的运行(linux运行java程序)
- Linux上善用Java:实现智能开发(linux 运行java)
- Java Redis一次实现无限数据加速的尝试(用java redis)
- 编程Oracle数据库中实现Java编程的突破之道(oracle使用java)