Java递归实现简单算法

1.斐波那契数列

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

2.求阶乘

package algorithm;
public class Algorithm_2 {
    public static void main(String[] args) {
        System.out.print(getNum(5));
    }
    /**
     * 求阶乘
     * n!=n*(n-1)*(n-2)*...*1
     * @param n
     * @return
     */
    public static int getNum(int n){
        if(n == 1){
            System.out.print(n + "=");
            return 1;
        }else {
            System.out.print(n + "*");
            return getNum(n-1) * n;
        }
    }
}

3.列出某个目录下所有子目录和文件

package algorithm;
import java.io.File;
public class Algorithm_3 {
    public static void main(String[] args) throws Exception {
        getDir("F:\\Java\\jdk\\db");
    }
    /**
     * 列出某个目录下所有子目录和文件
     * @param path
     * @return
     */
    public static 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() + "非Dir非File?!");
        }
    }
}

4.汉诺塔问题

package algorithm;
public class Algorithm_4 {
    private final static String from = "柱子A";
    private final static String mid = "柱子B";
    private final static String to = "柱子C";

    public static void main(String[] args) {
        move(5, from, mid, to);
    }
    /**
     * 汉诺塔
     * 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                 ;完成
     * @param n
     * @param from2
     * @param mid2
     * @param to2
     */
    public static void move(int n, String from2, String mid2, String to2){
        if(n == 1){
            System.out.println("移动盘子 " + n + " 从 " + from2 + " 到 " + to2);
        }else {
            move(n-1, from2, to2, mid2);
            System.out.println("移动盘子 " + n + " 从 " + from2 + " 到 " + to2);
            move(n-1, mid2, from2, to2);
        }
    }
}

5.二分法查找

package algorithm;
/**
 * 二分法查找值
 * 一定是有序表,升序降序都可以
 * 原理就是找中间值
 */
public class Algorithm_5 {

    public static void main(String[] args) {
        int[] array = {1,3,5,7,9,12,14,15,19,20,22,23,28,30};
        System.out.println(search(array, 0, array.length-1, 20));
    }
    /**
     * @param array 有序数组,但不限于数组
     * @param start 开始查找的数组下标
     * @param end 结束查找的数组下标
     * @param searchValue 要搜索的值
     * @return
     */
    public static 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;
        }
    }
}

结束