1 什么是递归？

✈️ 通俗点来说，递归就是让方法自己调用自己，每次调用自己时传入不同的变量。有助于将复杂的问题简单化，使代码更加简洁。

2 递归的执行机制

2.1 浅尝递归

😗 递归在内存中是如何执行的呢？其实总的来说，就一句话：谁调用还给谁的原则！ 为了便于大家理解我们来看一个例子：

阅读如下代码块，猜猜控制台会输出什么？

class Recursion{
    // 递归打印函数
    public void myPrint(int n){
        if(n > 1){
            myPrint(n-1);
        }
        System.out.println("n = " + n);
    }
}
public class Exercise1 {
    public static void main(String[] args) {
        Recursion r = new Recursion();
        r.myPrint(3);
    }
}

输出结果如下:

小伙伴看到这里可能会疑惑，为什么会是这个结果？别急，我们继续从内存角度一点点分析：

1. ⭐️ 首先程序进入 main栈，在堆区开辟一个空间用于存储对象，并让 r 指向该空间；
2. ⭐️ 开始 调用 myPrint 方法，程序在栈区开辟出了一个 myPrint栈独立空间（橙色），传入的参数初始值为 n = 3，满足 n > 1,继续执行 myPrint（3 - 1），递归调用；
3. ⭐️ 开辟另一个 myPrint栈空间（紫色），传入参数为 n = 2，满足 n > 1，继续执行 myPrint（2 - 1），递归调用；
4. ⭐️ 再次开辟一个 myPrint栈空间（粉色），传入参数 n = 1，不满足 n > 1，所以执行输出 n = 1的操作后该空间进程结束，回退到 myPrint栈空间（紫色）；
5. ⭐️ 此时打印 n = 2，该空间进程结束，再次回退，返回到 myPrint栈空间（橙色）；
6. ⭐️ 此时打印 n = 3，该空间进程也结束了，于是返回到 main栈，继续执行主函数未完成的操作。

具体示意图如下：

2.2 递归的重要规则

🅰️通过以上内容，大家一定对递归有了更深入的了解，需要注意的是样例中我们传入的参数是 基本数据类型，因此，递归的各个方法产生的栈互不影响。 如果我们传入的是一个引用数据类型，则由于数据存储在堆区，则会因为方法的调用相互产生影响。具体参考博客：

1.【JavaSE】深入理解类与对象 || 方法调用机制与方法的传参机制浅析

2.【JavaSE】数组的赋值机制（值拷贝与引用传递）、数组拷贝、数组反转与数组扩容

🍑 递归所满足的规则总结如下:

1. 执行一个方法的时候，就会 创建一个新的受保护的独立栈空间；
2. 如果方法传入的是基本数据类型，则 局部变量是独立的，不会相互影响；
3. 如果方法传入的是引用数据类型，比如数组，就会 共享该引用类型的数据；
4. 当一个方法执行完毕后，或者遇到 return语句，就会返回，满足谁调用就将结果返回给谁的原则；
5. 当方法执行完毕或者返回时，该方法的进程也将结束了。

3 递归练习

😎 说了那么多，又到了练习的环节啦！一定要自己思考后再看答案哦！！！

3.1 练习1 斐波那契

请用递归的方式求出斐波那契数列 1，1，2，3，5，8，13… …

要求：给定一个整数 n，能够求出斐波那契的第 n 项的值即可。

🍑 思路分析： 这应该算是递归的经典题型啦，我们来仔细观察一下斐波那契数列，可以发现除了第1项和第2项的值是1以外，其余各项的值 F(n) = F(n - 1) + F(n - 2)，其中 n 表示第几项。

🍎 参考代码：

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(fibonacci(4));
    }
    private static int fibonacci(int n){
        if(n == 1 || n == 2){
            return 1;
        }else {
            return fibonacci(n-1) + fibonacci(n-2);
        }
    }
}

3.2 练习2 猴子吃桃问题

有一堆桃子，猴子第一天吃掉了其中的一半，并多吃了一个！以后每天猴子都吃其中的一半，然后再多吃一个。当到第十天的时候，想再吃时（还没吃），发现桃子只剩下了1个。

问：最初桃子🍑 总数是多少?

🍑 思路分析如下:

day = 10时，只有 1 个桃子；

day = 9时，有 (day = 10 天的桃子数 + 1) * 2个桃子；

day = 8时，有（day = 9天的桃子数 + 1）* 2个桃子；

…

…

通过分析我们发现规律： 前一天的桃子数 = （后一天的桃子数 + 1）* 2

🍎 参考代码: (输出的答案为：1534)

public class Monkey {
    public static void main(String[] args) {
        System.out.println(monkeyEatPeaches(1));
    }
    private static int monkeyEatPeaches(int day){
        if(day == 10){
            return 1;
        }else if(day >= 1 && day <= 9){
            return (monkeyEatPeaches(day + 1) + 1) * 2;
        }else {
            System.out.println("输入错误");
            return -1;
        }
    }
}