什么是递归？

简单的理解就是：递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂问题,同时可以让代码变 得简洁

递归能解决什么问题？

1. 各种数学问题如∶8皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子的问题。
2. 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等。3. 将用栈解决的问题-->递归代码比较简洁

递归小案例 来理解递归调用机制

• 打印问题
• 阶乘问题

static 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;
            }
        }
    }

    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);
    }

打印问题的方法调用分析图

阶乘问题方法分析图

递归的重要规则

1. 执行一个方法时，就创建一个新受保护的独立空间（栈空间）
2. 方法的局部变量是独立的，不会相互影响，比如n变量
3. 如果方法中使用的是引用类型变量（比如数组，对象），就会共享该引用类型的数据。
4. 递归必须向退出递归的条件逼近，否则就是无限递归，出现StackOverflowError，死龟了
5. 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就
   将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。

既然我们已经知道递归的基本使用了，用递归解决下面问题看看

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

   /**
     * @description: 请使用递归的方式求出斐波那契数1，1，2，3，5，8，13..给你一个整数n,求出它的值是多
     * 1. 传入的数必须大于 0
     * 2. n = 1 斐波那契数 == 1
     * 2. n = 2 斐波那契数 == 1
     * 2. n >= 3 斐波那契数 等于前两数之和
     * @param:  n 表示获取第几位斐波拉契数
     * @return: 斐波那契数
     * @author Mr.luo
     * @date: 2021/12/5 1:41 下午
     */
    public static int fibonacci(int n){
        if(n >= 1){
            if(n == 1 || n == 2){
                return 1;
            } else {
                return fibonacci(n-1) + fibonacci(n-2);
            }
        } else {
            return -1;
        }
    }

2. 猴子吃桃子问题∶有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个!以后每天猴子都吃其中的一半，然后再多吃一个。当到第10天时，想再吃时（即还没吃）发现只有1个桃子了。问题∶最初共多少个桃子?

   /**
     * @description: 猴子吃桃子问题∶
     * 有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个!以后每天猴子都吃其中的一半，然后再多吃一个。
     * 当到第10天时，想再吃时（即还没吃）发现只有1个桃子了。问题∶最初共多少个桃子?
     * 思路分析：已知条件 ： 每天吃一半 再多吃 一个 ， 再第十天的时候只有一个桃子了
     * 逆向推导：
     * 第十天 day = 1 个
     * 第九天 day = (第十天 + 1) * 2
     * 第八天 day = (第九天 + 1) * 2
     * 规律：当天的桃子数量 = （前一天桃子数量 + 1） * 2
     * @author Mr.luo
     * @date: 2021/12/5 1:55 下午
     */
    public static int monkeyEatingPeach(int day){
        if (day == 10) {
            return 1;
        } else if(day > 0 && day <= 9) {
            return (monkeyEatingPeach(day + 1) +1) * 2;
        } else {
            System.out.println("day 输入错误");
        }
        return -1;
    }

我将在接下来的篇章里用递归思想解决 ：
8皇后问题，汉诺塔，阶乘问题，迷宫问题