什么是递归？
简单的理解就是：递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂问题,同时可以让代码变 得简洁
递归能解决什么问题？
- 各种数学问题如∶8皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子的问题。
- 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等。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);
}
打印问题的方法调用分析图
阶乘问题方法分析图
递归的重要规则
- 执行一个方法时，就创建一个新受保护的独立空间（栈空间）
- 方法的局部变量是独立的，不会相互影响，比如n变量
- 如果方法中使用的是引用类型变量（比如数组，对象），就会共享该引用类型的数据。
- 递归必须向退出递归的条件逼近，否则就是无限递归，出现StackOverflowError，死龟了
- 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就
将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。
既然我们已经知道递归的基本使用了，用递归解决下面问题看看
- 请使用递归的方式求出斐波那契数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;
}
}
- 猴子吃桃子问题∶有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个!以后每天猴子都吃其中的一半，然后再多吃一个。当到第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皇后问题，汉诺塔，阶乘问题，迷宫问题
