目录
1、什么是递归算法？
2、代码演示
2.1 直接递归
2.2 间接递归
2.3 递归栈内存溢出异常情况分析
3、递归三要素
4、递归经典例子学习
4.1 n的阶乘 - 代码演示
4.2 猴子吃桃 - 代码演示
5、递归总结：
1、什么是递归算法？
从形式上说，方法调用自身的形式就叫递归 递归分为两种情况：
直接递归（用的比较多）：方法自己调用自己
间接递归：方法调用其他方法 ，其他方法又回调原来方法。
2、代码演示
2.1 直接递归
方法自己调用自己
public class RecursionTest {
public static void main(String[] args) {
testRe();
}
private static void testRe(){
System.out.println("递归打印");
testRe();
}
}
2.2 间接递归
通过其他方法来回调自己
public class RecursionTest {
public static void main(String[] args) {
testRe();
}
private static void testRe(){
System.out.println("递归打印");
testRe1();
}
private static void testRe1(){
System.out.println("递归111打印");
testRe();
}
}
2.3 递归栈内存溢出异常情况分析
上面的两个例子中，都出现了StackOverflowError异常，原因是我们没有控制好终止，所以进入了递归的死循环。
我们调用一个方法时，在栈的方法区中会占用一个新的内存，而递归则是一直调用一直创建，如果不做好终止的控制，就会一直调用无穷无尽，就会出现栈内存溢出异常StackOverflowError
3、递归三要素
递归的公式递归的终结点递归的方向必须走向终结点
4、递归经典例子学习
4.1 n的阶乘 - 代码演示
这是最简单且经典的递归例子
公式：f(n) = f(n - 1) * n
//公式解释：5 * 4* 3 * 2 * 1
终结点：乘到1时，即n = 1
public class RecursionTest {
public static void main(String[] args) {
System.out.println(testRe(5));
}
private static int testRe(int n){
//终结点
if (n == 1){
return 1;
}else {
return testRe(n - 1) * n;
}
}
}
可以看到输出的结果为120
用一张图来解释程序执行的过程：
4.2 猴子吃桃 - 代码演示
面试常问经典例子
公式：f(n) - f(n) /2 -1 = f(n +1) 化简：2f(n) - f(n) + 2 = 2f(n+1) --> f(n) = 2f(n+1) +2
//公式解释：（第一天桃子数） 减去（第一天桃子数的一半）减去 （一个桃子）等于 （第二天的桃子数量）
终结点：第十天，桃子数等于1，即f(10) = 1;
我们求的是第一天的桃子数
直接套公式，丝滑得很啊!!!
public class RecursionTest {
public static void main(String[] args) {
System.out.println(peak(1)); //求的是第一天的桃子数
}
private static int peak(int day){
if (day == 10){
return 1; //终结点：当第十天时，桃子的数量为1
}else {
return 2 * peak(day+1) + 2; //直接套公式
}
}
}
最终结果是1534，同学们可以去验证一下
5、递归总结：
一定要找到递归三要素
递归的公式递归的终结点递归的方向必须走向终结点
最后直接套用公式就好了，非常丝滑的算法。
但是要注意的是，递归是非常耗内存的，要注意使用场景哦，非必要不使用递归算法，记得一定要找好终结点！
这就是我对递归算法理解，希望能帮到大家，有问题的地方欢迎大家一起讨论！
后续会不断更新作品，欢迎大家一起讨论学习。❤❤❤