一、递归缩写
🌱 YAML：是 SpringBoot 框架推荐的一种配置文件，它的全称是【YAML Ain’t a Markup Language（YAML 不是一种标记语言）】，可以看到 YAML 是一个句子的递归缩写。
🌱 GNU：是一个自由的操作系统，其内容软件完全以 GPL 方法发布，但它不包含具著作权的 Unix 代码。它的全称是【GNU's Not Unix（GNU 并非 Unix）】，GNU 也是一个句子的递归缩写。
二、递归调用
思考：如何计算 [1, n] 范围内的整数的累加和 ?
下面的代码通过【循环】的方式计算 [1, n] 范围内的累加和，本篇文章学习另一种求累加和的方式： 递归求和
public class RecursionTest {
public static void main(String[] args) {
// sumByCircular = 15
System.out.println("sumByCircular = " + sumByCircular(5));
}
/**
* 通过【循环】计算 [1, n] 范围内的整数的累加和
*/
private static int sumByCircular(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
}🍉【 分析】求 [1, n] 范围的累加和，可以理解为 求 [1, n-1] 范围的累加和, 然后再加 n
🍉 如： 求 [1, 5] 范围的累加和可如下思考：
🍉 ① 求 [1, 5] 范围的累加和，可以理解为 求 [1, 4] 范围的累加和, 然后再加 5
🍉 ② 求 [1, 4] 范围的累加和，可以理解为 求 [1, 3] 范围的累加和, 然后再加 4
🍉 ③ 求 [1, 3] 范围的累加和，可以理解为 求 [1, 2] 范围的累加和, 然后再加 3
🍉 ④ 求 [1, 2] 范围的累加和，可以理解为 求 [1, 1] 范围的累加和, 然后再加 2
(1) 递归方式求累加和
使用【递归】计算 [1, n] 范围内的整数的累加和的代码：
public class RecursionTest {
public static void main(String[] args) {
// sumByRecursion = 21
System.out.println("sumByRecursion = " + sumByRecursion(6));
}
/**
* 使用【递归】计算 [1, n] 范围的累加和
*/
private static int sumByRecursion(int n) {
if (n <= 1) return 1; // 递归终止条件
return n + sumByRecursion(n - 1);
}
}
如果递归没有终止条件 ❓
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!
