1、概念

递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。并且递归用到了虚拟机栈

2、能解决的问题

数学问题

  • 八皇后问题
  • 汉诺塔
  • 求阶乘
  • 迷宫问题
  • 球和篮子

各种排序算法

3、规则

  • 方法的变量是独立的，不会相互影响的

  • 如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据

  • 递归必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError

  • 当一个方法执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或

    者返回时，该方法也就执行完毕

4、迷宫问题

思路

  • 用一个二维矩阵代表地图
    • 1代表边界
    • 0代表未做过该地点
    • 2代表走过且能走得通
    • 3代表走过但走不通
  • 设置起点和终点以及每个地点的行走策略
    • 行走策略指在该点所走的方向的顺序，如 下->右->上->左（调用寻找路径的方法，使用递归）
  • 每次行走时假设该点能够走通，然后按照策略去判断，如果所有策略判断后都走不通，则该点走不通

图解

初始地图，假设圆点为终点

如以下->右->上->左的策略，路线如下

代码

public class MiGong {    //用0表示没有走过的路,用1表示墙    public static void main(String[] args) {        int[][] map = new int[8][7];//创建地图                //设置地图的墙体,用1来表示        for (int i = 0; i < 7; i++){            map[0][i] = 1;            map[7][i] = 1;        }        for (int i = 0; i < 8; i++){            map[i][0] = 1;            map[i][6] = 1;        }        map[3][1] = 1;        map[3][2] = 1;        System.out.println("迷宫地图:");        for (int i = 0; i < map.length; i++){            for (int j = 0; j < map[0].length; j++){                System.out.print(map[i][j]+" ");            }            System.out.println();        }        setWay(map,1,1);        System.out.println("启动走迷宫后:");        for (int i = 0; i < map.length; i++){            for (int j = 0; j 右->上->左                if (setWay(map,i+1,j)){                    return true;                }else if (setWay(map,i,j+1)){                    return true;                }else if (setWay(map,i-1,j)){                    return true;                }else if (setWay(map,i,j-1)){                    return true;                }else {                    map[i][j] = 3;                    return false;                }            }else {//非0的情况可能是1、2、3,直接false                return false;            }        }    }}

　　结果：