Java递归算法

本篇内容来自网络以及自己接触到的一些内容,尚未整理!

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();
	}
}