递归
是指某个方法在自己的方法体内直接或间接的调用自己。
作用和嵌套循环有些类似,很多地方可以互换使用;但在有些问题上只能使用递归实现;
例如:扫描某个文件夹下的所有Java文件,包括子文件夹下的Java文件。此时并不知道这个文件夹下最多有多少层子文件,所有无法使用嵌套循环来实现这样的扫描
实例:
package recursion;
import java.io.File;
import java.util.ArrayList;
import java.util.List;
/**
* 演示递归算法
* 使用递归扫描某文件夹下的所有文件(包含子文件夹下的文件)
* 对于这个需求使用循环很难实现
* 因为程序运行之前,并不知道文件夹下有多少层
* 所以就无法确定要嵌套多少层的循环
* @author 学霸联盟 - 赵灿
*/
public class RecursionDemo {
/**
* 扫描文件的方法
* @param file 扫描到的文件
* @param fileList 存储扫描结果
*/
public void scan(File file, List<File> fileList) {
// 首先通过判断保证这个file对象存在
if (file != null && file.exists() && fileList != null) {
// 如果这个file是文件
if (file.isFile()) {
//这里可以进行对文件的筛选;比如:选出后缀名为.java的文件
if(file.getName().endsWith(".java")){
// 将这个文件加入到集合中
fileList.add(file);
}
} else {
// 如果file对象不是文件,就说明是文件夹
//首先要获取文件夹下所有文件的数组
File[] files = file.listFiles();
//判断这个数组是否为null
if(files != null){
// 循环递归调用自己,并把文件夹对象file和存储文件的集合传入
for(File f:files){
//执行完此句代码,会重新在栈内存中创建一个新的scan方法的栈帧
//执行一次,就会创建一个新的栈帧。所以,这里有可能会出现栈内存用尽的错误
scan(f, fileList);
}
}
}
}
}
public static void main(String[] args) {
RecursionDemo rd = new RecursionDemo();
// 要扫描的文件夹,这里设定为E盘,即扫描E盘下所有的文件
File initFile = new File("E:\\");
//用于存储扫描结果的集合
List<File> fileList = new ArrayList<File>();
//调用扫描文件的方法,执行完此句代码,会在栈内存中创建一个scan方法的栈帧
rd.scan(initFile, fileList);
//循环输出扫描结果
for (File file : fileList) {
//输出文件全名
System.out.println(file.getPath());
}
}
}
递归和循环的区别
|
嵌套循环 |
递归 |
方法栈帧 |
如果循环内不调用任何方法,则循环永远只会使用这一个栈帧 |
调用一次方法,就要重新创建一个新的方法栈帧,可能会出现栈内存耗尽的错误 |
局部变量 |
如果某局部变量在循环语句之上声明,则这个变量只占用一个内存空间 |
如果某个局部变量在递归调用语句之上声明,则只要重建一个该方法的栈帧,这个局部变量就会在新建的方法栈帧中占用一次内存空间 |
版权声明:本文为博主原创文章,未经博主允许不得转载。
分享到:
相关推荐
java递归算法,java递归算法,java递归算法
.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法
Java二分查找递归算法
Java递归算法构造JSON树形结构,Java递归算法构造JSON树形结构Java递归算法构造JSON树形结构
java编写的递归算法的经典事例。 代码很短,没有点基础理解起来还真有点难度。很有挑战性。 不是我写的。这里只是分享一下。 功能是实现全排列。
java 数据结构 递归 八皇后 完美递归 java 数据结构 递归 八皇后 完美递归
递归算法详解递归算法详解递归算法详解递归算法详解
LCS问题 归并排序 矩阵链乘积问题 N皇后问题 贪心算法 快速排序 二分检索 求最大元素最小元素(分治算法) 求n个数的排列(递归)
* 消除递归: * 一个算法作为一个递归的方法通常从概念上很容易理解,但实际使用中递归的效率不高,在这种 * 情况下,把递归算法转换成非递归的算法是非常有用的,这种转换经常用到栈。 * * 递归和栈: *...
一个用JAVA编写的扫雷程序,原创! 可以输入界面的行列数和雷数,此程序的精髓在打开一个不是雷而且周围没有雷的格子时,用到了递归的思想。
java程序的递归算法,列出某个目录下的所有子目录和文件
18.递归算法与递归算法应用.ppt
ACM培训基础算法之递归PPT详解 包括递归的一些基础思想和一些经典例题
java实现的经典递归算法三例 十分的经典,可以学习一下
* 非递归的二分查找:二分查找也可以用非递归的算法,但是分治算法通常要回到递归。分治算 * 法常常是一个方法,在这个方法中含有两个对自身的递归的调用。 * * 分治算法:递归的二分查找是分治算法的一种...
算法分析实验报告:熟悉环境和递归算法、动态规划算法、贪心算法、回溯法
15个典型的递归算法的JAVA实现,求N的阶乘、欧几里德算法(求最大公约数)、斐波那契数列、汉诺塔问题、树的三种递归遍历方式、快速排序、折半查找、图的遍历、归并排序、八皇后问题(回溯、递归)、棋盘覆盖(分治,...
小小学习,C语言数据结构,中序遍历二叉树非递归算法
5!递归算法和非递归算法,面试专用,适合新手