递归 - 《java基础》

递归的流程图

递归就是自己调用自己。递归的思想将一个未知的问题拆分成一个个重复的小问题。

简单说程序调用自身的编程技巧叫递归。递归的思想是把一个大型复杂问题层层转化为一个与原问题规模更小的问题，问题被拆解成子问题后，递归调用继续进行，直到子问题无需进一步递归就可以解决的地步为止。

使用递归需要避免出现死循环，为了确保递归正确工作，递归程序应该包含2个属性：

基本情况（bottom cases），基本情况用于保证程序调用及时返回，不在继续递归，保证了程序可终止。

递推关系（recurrentce relation），可将所有其他情况拆分到基本案例。

public int Recursion(int count){
 if(count > 0){
     Recursion(--count);
     System.out.println(count);
 }
 return count;
}

```java public class Fibonacci{ public static void main(String[] args){

 int[] count = new int[10];
 fibonacciS(count,count.length - 1);

} //数组，求数组的索引 public static void fibonacciS(int[] count,int n){

 if (n != 1){
     fibonacciS(count,n-1);
     count[n] = count[n - 1] + count[n - 2];
     System.out.println(count[n]);
 }else{
     count[0] = 1;
     count[1] = 1;
     System.out.println(1);
     System.out.println(1);
 }

}

```csharp
//汉诺塔问题
class  TowerOfHanoi{
    //输入：A = [2, 1, 0], B = [], C = []
    //输出：C = [2, 1, 0]
    //移动多少个,起始数组,工具数组,目标数组
    public void towerOfHanoi(int count, List<Integer> start, List<Integer> target, List<Integer> instrument){
        if (count != 0){
            //将起始的count-1个数组移动到工具数组(目标数组为中间数组)
            towerOfHanoi(count - 1,start,instrument,target);
            //将起始数组中最大的移动到目标数组
            instrument.add(start.get(start.size() - 1));
            start.remove(start.size() - 1);
            //将工具的count-1个数组移动到目标数组(起始数组为中间数组)
            towerOfHanoi(count - 1,target,start,instrument);
        }
    }
}

public class EightQueens{
    public static void main(String[] args){
        //棋盘的行和列
        int count = 8;
        int[] eight = new int[count];

        eightQueens(eight, 0);
        System.out.println(eights);
    }
    static int eights = 0;
    //数组    行数-1
    public static void eightQueens(int[] eight,int n){
        //0true 1false
        int[] count = new int[eight.length];
        for (int i = 0;i < count.length;i++){
            count[i] = 0;
        }
        //判断n行可以放的列
        for (int i = 0;i < n;i++){
            count[eight[i]]=1;
            if(eight[i] - n + i >= 0){
                count[eight[i] - n + i]=1;
            }if(n + eight[i] - i < eight.length){
                count[n + eight[i] - i]=1;
            }
        }
        for (int i = 0;i < count.length;i++){
            if (count[i] == 0){
                eight[n] = i;
                //结果通过输出
                if (n == eight.length - 1){
                    for (int j = 0; j < eight.length; j++) {
                        System.out.print(eight[j] + " ");
                    }
                    System.out.println();
                    eights++;
                }
                eightQueens(eight,n+1);
            }
        }
    }
}

public class Maze{
    public static void main(String[] arge){
        int[][] maze = new int[8][7];
        //0=空   1=障碍物   2=空1   3=障碍物1    4=目的地
        maze[0] = new int[]{1, 1, 1, 1, 1, 1};
        maze[1] = new int[]{1, 0, 0, 0, 0, 1};
        maze[2] = new int[]{1, 0, 1, 0, 1, 1};
        maze[3] = new int[]{1, 1, 1, 0, 0, 1};
        maze[4] = new int[]{1, 0, 0, 0, 0, 1};
        maze[5] = new int[]{1, 0, 1, 1, 1, 1};
        maze[6] = new int[]{1, 0, 0, 0, 4, 1};
        maze[7] = new int[]{1, 1, 1, 1, 1, 1};
        mazes(maze,1,1);
    }
    //地图 x y 方向
    public static boolean mazes(int[][] maze,int x,int y){
        if (maze[x][y] == 4){
            for(int i = 0;i < maze.length;i++){
                for (int j = 0;j < maze[0].length;j++){
                    System.out.print(maze[i][j]+" ");
                }
                System.out.println();
            }
        }else{
            if (maze[x][y] == 0){
                maze[x][y] = 2;
                //下
                if (mazes(maze,x+1,y)){
                    return true;
                }
                //左
                else if (mazes(maze,x,y-1)){
                    return true;
                }
                //上
                else if (mazes(maze,x-1,y)){
                    return true;
                }
                //右
                else if (mazes(maze,x,y+1)){
                    return true;
                }
                else {
                    maze[x][y] = 3;
                    return false;
                }
            }else{
                return false;
            }
        }
        return true;
    }
}

八皇后测试网址
https://zhouxuewen.gitee.io/game/

递归的流程图

递归 - 图1
引用：
全面理解递归 - Young Wang的文章 - 知乎 https://zhuanlan.zhihu.com/p/150562212