本篇内容来自网络以及自己接触到的一些内容,尚未整理!
JAVA递归算法
递归算法:是一种直接或间接调用自身方法或函数的算法.JAVA递归算法就是基于JAVA语言实现的递归算法.
递归的实质就是把复杂的问题分析为若干个相对简单的子问题,一直分解下去,直到子问题有答案为止,也就是说到了递归的出口.递归算法对解决一大类问题很有效,它可以使算法简洁和易于理解.
递归算法的特点:
1.递归就是方法里调用自身.
2.在使用递归时,必须有一个明确的递归出口,也就是结束递归的条件.
3.递归算法通常显得很简洁,但递归算法解题的运行效率较低,所以一般不提倡使用递归算法设计程序.
4.在递归调用的过程中,系统为第一层的返回点,局部变量等开辟了栈来存储.递归次数过多容易造成栈溢了,所以一般不提但是用递归算法设计程序.
递归算法所体现的“重复”一般有三个要求:
一是每次调用在规模上都有所缩小(通常是减半);
二是相邻两次重复之间有紧密的联系,前一次要为后一次做准备(通常前一次的输出就作为后一次的输入);
三是在问题的规模极小时必须用直接给出解答而不再进行递归调用,因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件),无条件递归调用将会成为死循环而不能正常结束。
java递归算法实例一: 求解Fibonacci数列的第10个位置的值?
问题描述:求解Fibonacci数列的第10个位置的值?(斐波纳契数列(Fibonacci Sequence),又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*))
java递归算法实例二: 求从1加到5的或者求5的阶乘.
/** * java递归:求从1加到5的和 */ public class RecursionTest { //递归算法 public static int sum(int n){ if(n==1){ return 1; }else{ return n+sum(n-1); } } public static void main(String[] args) { System.out.println(sum(5)); } }
先分析一下执行的流程:
n=5时,执行sum(5)方法,返回的结果为:5 + sum(4)
n=4时,执行sum(4)方法,返回的结果为:4 + sum(3)
n=3时,执行sum(3)方法,返回的结果为:3 + sum(2)
n=2时,执行sum(2)方法,返回的结果为:2 + sum(1)
n=1时,执行sum(1)方法,返回的结果为:1
再向上返回,依次执行:
2+1
3+(2+1)
4+(3+2+1)
5+(4+3+2+1) = 15
思路应该是这样的:
要知道从1加到5的和,先得知道从1加到4的和,即:5+sum(4)
要知道从1加到4的和,先得知道从1加到3的和,即:4+sum(3)
要知道从1加到3的和,先得知道从1加到2的和,即:3+sum(2)
要知道从1加到2的和,先得知道从1加到1的和,即:2+sum(1)
从而很容易看出,递归的出口为1也就是sum(1)的值为1
再看一个例子,求5的阶乘,代码如下:
/** * java递归算法:求5的阶乘. */ public class RecursionTest01 { //求n的阶乘 public static int multiply(int n){ if(n==1){ return 1; }else{ return n*multiply(n-1); } } public static void main(String[] args) { System.out.println(multiply(5)); } }java递归算法实例三:深度遍历目录文件:
package io; import java.io.File; /* * 需求:对指定的目录进行所有内容的列出(包含子目录中的内容),也可以理解为深度遍历. * 注意不要去遍历:C盘因为它里边有许多系统目录,没有权限访问,会产生空指针, * 也不要遍历其他系统根目录如d:\\或e:\\因为:它们之中如果有系统文件也会产生空指针. * */ public class _18Filetest { public static void main(String[] args) { File dir=new File("D:\\Music"); listAll(dir,0); } /* 深度遍历文件夹:按如下的格式输出. * * |--Music * | |--KwDownload.txt * | |--L-聆听 * | | |--100413 * | | | |--002-I believe I can fly.lrc * | | | |--002-I believe I can fly.mp3 * */ private static void listAll(File dir,int level) { System.out.println(getSpace(level)+dir.getName()); level++; //获取指定目录下当前的所有文件夹或者文件对象. //listFiles()方法返回的是File对象,对象中封装了许多有用信息.而list只得到String类型的文件名. //listFiles()方法返回的时当前目录下的所有文件和目录对象,所以要想深度遍历必须使用递归调用. File[] files=dir.listFiles(); //对于数组的遍历如果不想操作脚标就使用foreach.如果想就使用for. for(int i=0;i<files.length;i++){ if(files[i].isDirectory()){ listAll(files[i],level); }else{ System.out.println(getSpace(level)+files[i].getName()); } } } private static String getSpace(int level){ StringBuilder sb=new StringBuilder(); sb.append("|--"); for(int i=0;i<level;i++){ sb.insert(0, "| ");//在字符串的最前面加入"| " } return sb.toString(); } }
相关推荐
Java递归算法构造JSON树形结构,Java递归算法构造JSON树形结构Java递归算法构造JSON树形结构
java递归算法,java递归算法,java递归算法
Java递归算法
java编写的递归算法的经典事例。 代码很短,没有点基础理解起来还真有点难度。很有挑战性。 不是我写的。这里只是分享一下。 功能是实现全排列。
主要介绍了Java递归算法遍历部门代码示例,具有一定借鉴价值,需要的朋友可以参考下。
简单叙述递归算法在java编程中的应用,使用递归的利弊。
说明地址:https://wenku.baidu.com/view/9bc0273750e2524de4187ec9.html?from_page=view&from_mod=download;
Java递归算法是基于Java语言实现的递归算法。递归算法对解决一大类问题很有效,它可以使算法简洁和易于理解。接下来通过本文给大家介绍Java递归算法相关知识,感兴趣的朋友一起学习吧
数据存储结构未多级时,查询某一级以下的数据时,通过递归算计可以取出所需要的数据
主要介绍了Java递归算法,通过两则示例分析了Java递归算法实现阶乘与求和的具体操作技巧,需要的朋友可以参考下
在本篇文章里小编给大家整理了关于java递归算法的实例内容,以及相关知识点总结,需要的朋友们可以学习下。
本文主要对经典的兔子案例分析,来进一步更好的理解和学习java递归算法,具有很好的参考价值,需要的朋友一起来看下吧
Java二分查找递归算法
18.递归算法与递归算法应用.ppt
15个典型的递归算法的JAVA实现,求N的阶乘、欧几里德算法(求最大公约数)、斐波那契数列、汉诺塔问题、树的三种递归遍历方式、快速排序、折半查找、图的遍历、归并排序、八皇后问题(回溯、递归)、棋盘覆盖(分治,...
主要介绍了java递归算法实例分析,具有一定借鉴价值,需要的朋友可以参考下。
java实现的经典递归算法三例 十分的经典,可以学习一下
* 情况下,把递归算法转换成非递归的算法是非常有用的,这种转换经常用到栈。 * * 递归和栈: * 递归和栈之间有着紧密的联系,大部分的编译器使用栈实现递归的。 * * 调用方法的时候发生什么: * 1. ...