方法递归调用

阶乘问题

public class Recursion01 { 

	//编写一个main方法
	public static void main(String[] args) {

		T t1 = new T();
		t1.test(4);//输出什么？ n=2 n=3 n=4
		int res = t1.factorial(5); 
		System.out.println("5的阶乘 res =" + res);
	}
}

class T {
	//分析
	public  void test(int n) 
		if (n > 2) {
			test(n - 1);
		} 
		System.out.println("n=" + n);
	}

	//factorial 阶乘
	public  int factorial(int n) {
		if (n == 1) {
			return 1;
		} else {
			return factorial(n - 1) * n;
		}
	}


}

用递归的方式求出斐波那契数1，1，2，3，5，8，13…给你一个整数，求出它的值是多少？

public class RecursionExercise01 { 

	//编写一个main方法
	public static void main(String[] args) {

		T t1 = new T();
		// int n = 7;
		// int res = t1.fibonacci(n);
		// if(res != -1) {
		// 	System.out.println("当n="+ n +" 对应的斐波那契数=" + res);
		// } 
		// 
		//桃子问题
		int day = 0;
		int peachNum = t1.peach(day);
		if(peachNum != -1) {
			System.out.println("第 " + day + "天有" + peachNum + "个桃子");
		}
	}
}

class T {
		/*
		请使用递归的方式求出斐波那契数1,1,2,3,5,8,13...给你一个整数n，求出它的值是多
		思路分析
		1. 当n = 1 斐波那契数 是1
		2. 当n = 2 斐波那契数 是1
		3. 当n >= 3  斐波那契数 是前两个数的和
		4. 这里就是一个递归的思路
		 */
	
		public int fibonacci(int n) {
			if( n >= 1) {
				if( n == 1 || n == 2) {
					return 1;
				} else {
					return fibonacci(n-1) + fibonacci(n-2);
				}
			} else {
				System.out.println("要求输入的是n>=1的整数");
				return -1;
			}
		}

		/*
		猴子吃桃子问题：有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个！
		以后每天猴子都吃其中的一半，然后再多吃一个。当到第10天时，
		想再吃时（即还没吃），发现只有1个桃子了。问题：最初共多少个桃子？
		
		思路分析 逆推
		1. day = 10 时 有 1个桃子
		2. day = 9 时  有 (day10 + 1) * 2 = 4
		3. day = 8 时  有 (day9 + 1) * 2 = 10
		4. 规律就是  前一天的桃子 = (后一天的桃子 + 1) *2//就是我们的能力
		5. 递归
		 */
		public int peach(int day) { 
			if(day == 10) {//第10天，只有1个桃
				return 1; 
			} else if ( day >= 1 && day <=9 ) {
				return (peach(day + 1) + 1) * 2;//规则，自己要想
			} else {
				System.out.println("day在1-10");
				return -1;
			}
		}
	
}

迷宫问题

public class Object01 {

    //编写一个main方法
    public static void main(String[] args) {

        //思路
        //1. 先创建迷宫，用二维数组表示 int[][] map = new int[8][7];
        //2. 先规定 map 数组的元素值: 0 表示可以走 1 表示障碍物

        int[][] map = new int[8][7];
        //3. 将最上面的一行和最下面的一行，全部设置为1
        for(int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //4.将最右面的一列和最左面的一列，全部设置为1
        for(int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        map[2][2] = 1; //测试回溯
        // map[2][1] = 1;
        // map[2][2] = 1;
        // map[1][2] = 1;

        //输出当前的地图
        System.out.println("=====当前地图情况======");
        for(int i = 0; i < map.length; i++) {
            for(int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");//输出一行
            }
            System.out.println();
        }

        //使用findWay给老鼠找路
        T t1 = new T();
        //下右上左
        t1.findWay(map, 1, 1);

        System.out.println("\n====找路的情况如下=====");

        for(int i = 0; i < map.length; i++) {
            for(int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");//输出一行
            }
            System.out.println();
        }
    }
}

class T  {

    //使用递归回溯的思想来解决老鼠出迷宫

    //1. findWay方法就是专门来找出迷宫的路径
    //2. 如果找到，就返回 true ,否则返回false
    //3. map 就是二维数组，即表示迷宫
    //4. i,j 就是老鼠的位置，初始化的位置为(1,1)
    //5. 因为我们是递归地找路，所以先规定 map 数组的各个值的含义
    //   0 表示可以走 1 表示障碍物 2 表示可以走 3 表示走过，但是走不通是死路
    //6. 当map[6][5] =2 就说明找到通路,就可以结束，否则就继续找.
    //7. 先确定老鼠找路策略 下->右->上->左

    public boolean findWay(int[][] map , int i, int j) {
        if(map[6][5] == 2) {//说明已经找到
            return true;
        } else {
            if(map[i][j] == 0) {//当前这个位置0,说明表示可以走
                //我们假定可以走通
                map[i][j] = 2;
                //使用找路策略，来确定该位置是否真的可以走通
                //下->右->上->左
                if(findWay(map, i + 1, j)) {//先走下
                    return true;
                } else if(findWay(map, i, j + 1)){//右
                    return true;
                } else if(findWay(map, i-1, j)) {//上
                    return true;
                } else if(findWay(map, i, j-1)){//左
                    return true;
                } else {
                    map[i][j] = 3;
                    return false;
                }
            } else { //map[i][j] = 1 , 2, 3
                return false;
            }
        }
    }

    //修改找路策略，看看路径是否有变化
    //下->右->上->左 ==> 上->右->下->左
    public boolean findWay2(int[][] map , int i, int j) {
        if(map[6][5] == 2) {//说明已经找到
            return true;
        } else {
            if(map[i][j] == 0) {//当前这个位置0,说明表示可以走
                //我们假定可以走通
                map[i][j] = 2;
                //使用找路策略，来确定该位置是否真的可以走通
                //上->右->下->左
                if(findWay2(map, i - 1, j)) {//先走上
                    return true;
                } else if(findWay2(map, i, j + 1)){//右
                    return true;
                } else if(findWay2(map, i+1, j)) {//下
                    return true;
                } else if(findWay2(map, i, j-1)){//左
                    return true;
                } else {
                    map[i][j] = 3;
                    return false;
                }
            } else { //map[i][j] = 1 , 2, 3
                return false;
            }
        }
    }
}

汉诺塔问题

public class Object01 {

    //编写一个main方法
    public static void main(String[] args) {

        Tower tower = new Tower();
        tower.move(64, 'A', 'B', 'C');
    }
}

class Tower { //方法
    //num 表示要移动的个数, a, b, c 分别表示A塔，B 塔, C 塔
    public void move(int num , char a, char b ,char c) {
        //如果只有一个盘 num = 1
        if(num == 1) {
            System.out.println(a + "->" + c);
        } else {
            //如果有多个盘，可以看成两个 , 最下面的( 1 )和上面的所有盘( num-1 )
            //(1)先移动上面所有的盘到 b, 借助 c
            move(num - 1 , a, c, b);
            //(2)把最下面的这个盘，移动到 c
            System.out.println(a + "->" + c);
            //(3)再把 b塔的所有盘，移动到c ,借助a
            move(num - 1, b, a, c);
        }
    }
}