算法——递归算详细总结

import org.junit.jupiter.api.Test;

/**
 * 斐波那契数列
 * @author wydream
 *
 */

public class Algorithm_1 {

	/**
     * 用递归实现斐波那契数列,适用于求解比较小的位置数值
     * 0 1 1 2 3 5 8 13 21...
     * @param n
     * @return
     */
	
	public int getNum(int n) {
		if(n<=2) {
			return 1;
		}else {
			return getNum(n-1)+getNum(n-2);
		}
	}
	
	@Test
	public void test() {
		System.out.println(getNum(6));
	}
	
}

import org.junit.jupiter.api.Test;

public class Algorithm_2 {
	
	public int getSum(int n) {
		//当n=1时，直接返回
		if(n==1) {
			System.out.print(n + "=");
			return n;
		}else {//n>1时,递归调用getSum方法,求出n*n-1的结果
			System.out.print(n + "*");
			return n*getSum(n-1); 
		}
	}
	
	@Test
	public void test() {
		System.out.println(getSum(4));
	}

}

import java.io.File;

import org.junit.jupiter.api.Test;

/**
 * 列出某个目录下所有子目录和文件
 * @author wydream
 *
 */

public class Algorithm_3 {

	public void getDir(String path) throws Exception{
		File file=new File(path);
		if(file.isDirectory()) {
			System.out.println("Dir --" + file.getPath());
			File[] fileArr=file.listFiles();
			for(File f:fileArr) {
				getDir(f.getPath());
			}
		}else if(file.isFile()) {
			System.out.println("File--"+file.getPath());
		}else {
			throw new Exception(file.getPath());	
		}
	}
	
	@Test
	public void test()throws Exception {
		getDir("D:\\software\\JavaSoft\\eclipse\\eclipse");//这里的目录换成你自己电脑上的目录即可
	}
}

import org.junit.jupiter.api.Test;

/**
 * 汉诺塔问题
 * @author wydream
 *
 */

public class Algorithm_4 {

	private final static String FROM="柱子A";
	private final static String MID="柱子B";
	private final static String TO="柱子C";
	
	/**
	 * 汉诺塔
     * func:
     * if n!=0 then          ;预定值
     * func(n-1, a, c, b)    ;将n-1个盘子由a移动到b，以c为辅助柱子（注意参数顺序）
     * move a[n] to c        ;将a上的最后一个盘子移动到c
     * func(n-1, b, a, c)    ;将n-1个盘子由b移动到c，以a为辅助柱子
     * endif                 ;完成
	 */
	public void move(int n,String from,String mid,String to) {
		if(n==1) {
			System.out.println("移动盘子 " + n + " 从 " + from + " 到 " + to);
		}else {
			move(n-1,from,to,mid);
			System.out.println("移动盘子 " + n + " 从 " + from + " 到 " + to);
			move(n-1,mid,from,to);
		}
	}
		
	@Test
	public void test() {
		move(3,FROM,MID,TO);
	}
	
}

import org.junit.jupiter.api.Test;

/**
 *  
 * 二分法查找值
 * 一定是有序表,升序降序都可以
 * 原理就是找中间值
 *
 * @author wydream
 *
 */

public class Algorithm_5 {
	
	public int search(int []array,int start,int end ,int searchValue) {
		
		if(array!=null&&array.length>0) {
			int middle=(start+end)/2;
			int middleValue=array[middle];
			if(searchValue==middleValue) {
				return middle;
			}else if(searchValue<middleValue){
				//查询值小于中值,在中值前面再次搜索,缩小范围
				return search(array,start,middle-1,searchValue);
			}else {
				//查询值大于中值,在中值后面再次搜索,缩小范围
				return search(array,middle+1,end,searchValue);
			}
		}else {
			return -1;
		}
		
	}
	
	@Test
	public void test() {
		int[] arr= {2,3,6,9,13,18,20,22,24,29,30,45,67,88};
		System.out.println(search(arr, 0, arr.length-1, 20));
	}

}