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递归解决九连环问题
总结
到此这篇关于Java实现简单的递归操作的文章就介绍到这了,更多相关Java递归操作内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
- 这篇文章主要介绍了Java连接数据库oracle中文乱码解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-05-16