文章目录

  • 一、递归缩写
  • 二、递归调用
    • (1) 递归方式求累加和
    • (2) 递归内存分析
  • 三、递归调用（概念）
  • 四、递归调用举例
  • 五、递归注意事项
  • 六、斐波那契数列
  • 七、猴子吃桃

一、递归缩写

YAML：是 SpringBoot 框架推荐的一种配置文件，它的全称是【YAML Ain’t a Markup Language（YAML 不是一种标记语言）】，可以看到 YAML 是一个句子的递归缩写。

GNU：是一个自由的操作系统，其内容软件完全以 GPL 方法发布，但它不包含具著作权的 Unix 代码。它的全称是【GNU’s Not Unix（GNU 并非 Unix）】，GNU 也是一个句子的递归缩写。

二、递归调用

思考：如何计算 [1, n] 范围内的整数的累加和 " />
如果递归没有终止条件 ❓
StackOverflowError（栈溢出）

(2) 递归内存分析

int sum = sumByRecursion(3);

执行上面代码，JVM 栈空间情况如下图：

递归调用若没有终止条件，将会一直消耗栈空间
最终会导致栈内存溢出（Stack OVerflow）
递归必须要有一个明确的终止条件（边界条件、递归基）

三、递归调用（概念）

方法中调用方法本身，每次调用时传入不同的参数。
递归提供编程者一个解决复杂问题的思路。

四、递归调用举例

看下面的代码, 思考输出结果：

public class RecursionDemo {   public static void main(String[] args) {       test(5);       /*           output:                    n = 2                   n = 3                   n = 4                   n = 5        */   }   private static void test(int n) {       if (n > 2) {           test(n - 1);       }       System.out.println("n = " + n);   }}

public class RecursionDemo {    public static void main(String[] args) {        test(5); // 只输出：n = 2    }    private static void test(int n) {        if (n > 2) {            test(n - 1);        } else {            System.out.println("n = " + n);        }    }}

通过递归计算阶乘：

public class RecursionDemo {    public static void main(String[] args) {        int result = factorial(5);        // result = 120        System.out.println("result = " + result);    }    private static int factorial(int n) {        // 如果 n 小于等于 1, 默认认为阶乘结果是 1         if (n <= 1) return 1;        return factorial(n - 1) * n;    }}

五、递归注意事项

调用方法会在栈空间分配一块新的、独立的、受保护的栈空间（栈帧）
方法的局部变量是独立的，不会相互受影响
调用递归方法的参数必须向退出递归的条件逼近，否则会导致无限递归，进而导致 StackOverflowError（栈溢出）

六、斐波那契数列

斐波那契数列数的几何模型在大自然、化学、生活中经常存在。

斐波那契数列：Fibonacci sequence
斐波那契数列：黄金分割数列
斐波那契数列： 兔子数列
斐波那契数列：由数学家莱昂纳多 斐波那契提出的

斐波那契数列描述：有一列数，前两个数是1，从第3个数开始，后面的数都是它的前面的两个数之和，如此规则构成的一系列数就是斐波那契数列。
斐波那契数列举例： 1、1、2、3、5、8、13、21、34、55、89

用代码实现：输入一个数字（代表斐波那契数列的第几项），打印斐波那契数列第几项的值

public class RecursionDemo {    public static void main(String[] args) {        // 89        System.out.println(fibonacci(11));    }    /**     * 递归求斐波那契数列的第 n 项的值     */    private static int fibonacci(int n) {        if (n <= 2) return 1;        return fibonacci(n - 1) + fibonacci(n - 2);    }}

递归方式实现斐波那契数列非常地不合适，但也是一种方法（以后讨论它的另外一种方法）

七、猴子吃桃

Monkey 有一篮子的桃子 ，不知具体多少个。
Monkey 第一天吃了桃子 总数的一半，并多吃一个。
以后猴子 每天都吃其中的一半，并多吃一个。
第十天的时候就只有1个桃子了。
问：篮子里面一开始有多少个桃子 ？

分析:

已知条件：
① 第十天只有1个桃子
② 每天吃当前桃子总数的一半，并多吃一个
推导
令 day(n) 是第 n 天的桃子数
① day(10) = 1
② day(9) = 4 【day(9) / 2 - 1 = day(10)】 第9天的桃子数的一半，再减1要等于第10天的桃子数
③ day(8) = 10 【day(8) / 2 - 1 = day(9)】 第8天的桃子数的一半，再减1要等于第9天的桃子数
④ day(7) = 22 【day(7) / 2 - 1 = day(8)】 第7天的桃子数的一半，再减1要等于第8天的桃子数
⑤ day(6) = 46 【day(6) / 2 - 1 = day(7)】 第6天的桃子数的一半，再减1要等于第7天的桃子数
…
通项公式
day(n) = day(n-1) / 2 - 1【当天的桃子数等于前一天的桃子数减一半，再减1】
化简得：day(n-1) = (day(n) + 1) * 2 【前一天的桃子数等于当天的桃子数加1之后乘以2】
最终：day(n) = (day(n +1) + 1) * 2【当天的桃子数等于后一天的桃子数加1后乘以2】

代码实现：

public class MonkeyPeachDemo {    public static void main(String[] args) {        // 第1天的桃子数：1534        System.out.println("第1天的桃子数：" + dayPeach(1));    }    private static int dayPeach(int d) {        if (d == 10) return 1;        return (dayPeach(d + 1) + 1) * 2;    }}

若发现错误，请不吝赐教。Have a nice day!