Java一些简单的递归算法

么么哒:

分享一些Java中一些简单的小算法

递归算法简单的来说就是自己调用自己,可以把一些复杂的问题转化成类似的小问题,然后通过调用自己求解,跟框架的 write less,do more的差不多.

但是在使用递归之后,虽然代码量会大大减少看起来很简洁,但是递归算法运行效率很低,而且很容易造成死循环.虽然不推荐开发使用,但对于自己理解一些复杂的问题还是很方便的.

下面就是几个简单的例子:

遍历文件夹

要求遍历出指定文件夹下的所有子文件以及子文件夹里的子文件

public class recursion {
    public static void main(String[] args) {
       
        File file = new File(path);
        showFileOfDir(file);
    }
    
    //遍历文件夹的方法
    public static void showFileOfDir(File dir) {
        
        //获取到当前文件夹的所有子文件以及子文件夹
        File[] files = dir.listFiles();
        
        //循环遍历
        for (File file : files) {
            //如果是文件夹,再次遍历
            if (file.isDirectory()) {

                showFileOfDir(file);
                
            } else {
            //是普通的文件就直接打印输出
                System.out.println(file);
            }
        }
        
    }
}

爬楼梯算法

假设有N阶台阶,每次上的时候只能跨一阶或者两阶,求一共有多少种方法爬上这个台阶

public class climbStairs {
    
    public static void main(String[] args) {
        System.out.println(climb(20));
    }
    
    public static int climb(int n) {
        
        //定义一个变量存储总数
        int i = 1;
        
        //0阶直接返回0值
        if (n <= 0) {
            return 0;
        }
        
        //一阶的话只有一种方法
        if (n == 1) {
            return i;
        }
        
        //两阶两种方法
        if (n == 2) {
            i++;
            return i;
        } else {
            //大于两阶,那么每跨出一步都会有两种可能
            return climb(n - 1) + climb(n - 2);
        }
    }
}

迷宫

利用二维数组可以做出一个简单的迷宫,然后用递归算法找出从[0, 0]入口出到[i, j]出口的路线

1 1 1 0 0 1 0 1 0 0 
0 0 1 1 1 0 0 0 0 0 
1 0 1 0 0 0 1 1 1 1 
1 1 1 1 1 0 0 0 1 1 
0 0 0 0 1 1 1 1 0 0 
1 0 1 0 0 0 0 1 0 0 
1 0 0 1 1 1 1 1 1 1 

假如1是有效的路线,0是无效的路线,怎么快速找出正确的路线

public class maze {

    //把走过的但是无效的路线换成3
    private final int TRIED = 3;
    //把正确有效的数字换成2打印输出
    private final int PATH = 2;

    private int[][] grid = {
            { 1, 1, 1, 0, 0, 1, 0, 1, 0, 0 },
            { 0, 0, 1, 1, 1, 0, 0, 0, 0, 0 },
            { 1, 0, 1, 0, 0, 0, 1, 1, 1, 1 }, 
            { 1, 1, 1, 1, 1, 0, 0, 0, 1, 1 },
            { 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 },
            { 1, 0, 1, 0, 0, 0, 0, 1, 0, 0 }, 
            { 1, 0, 0, 1, 1, 1, 1, 1, 1, 1 } 
            };

    //判断是否越界和是否有效
    private boolean valid(int row, int column) {

        boolean result = false;

        if (row >= 0 && row < grid.length && column >= 0 && column < grid[row].length)

            if (grid[row][column] == 1) {

                result = true;

            }

        return result;
    }
    
    
    public String toString() {
        
        String result = "\n";
        
        for (int row = 0; row < grid.length; row++) {
        
            for (int column = 0; column < grid[row].length; column++) {
            
                result += grid[row][column] + " ";
            
            }
        
            result += "\n";
    
        }
        
        return result;
    }

    //调用自己判断四周是否为有效的路径
    public boolean traverse(int row, int column) {
        
        boolean done = false;

        if (valid(row, column)) {
            
            //如果已经来过这个地方,打印3
            grid[row][column] = TRIED;
        
            if (row == grid.length - 1 && column == grid[0].length - 1) {
                done = true;
                
            }else {
                done = traverse(row + 1, column);// down
                if (!done)
                    done = traverse(row, column + 1);// right
                if (!done)
                    done = traverse(row - 1, column);// up
                if (!done)
                    done = traverse(row, column - 1);// left
            }
            if (done)
                grid[row][column] = PATH;
        }
        return done;
    }

    public static void main(String[] args) {
        Demo1 maze = new Demo1();
        System.out.println(maze);
        if (maze.traverse(0, 0))
            System.out.println("The maze was successfully travelled!");
        else
            System.out.println("There is no possible path.");
        System.out.println(maze);
    }
}


最后结果是这样的
2 2 2 0 0 1 0 1 0 0 
0 0 2 1 1 0 0 0 0 0 
1 0 2 0 0 0 1 1 1 1 
1 1 2 2 2 0 0 0 1 1 
0 0 0 0 2 2 2 2 0 0 
1 0 1 0 0 0 0 2 0 0 
1 0 0 1 1 1 1 2 2 2