非零基础自学Java (老师：韩顺平) 第7章 面向对象编程(基础部分) 7.4 方法递归调用

非零基础自学Java (老师：韩顺平)

✈【【零基础 快速学Java】韩顺平 零基础30天学会Java】

第7章 面向对象编程(基础部分)

7.4 方法递归调用

7.4.1 基本介绍

递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂问题,同时可以让代码变
得简洁

7.4.2 递归能解决什么问题

• 各种数学问题如:8皇后问题，汉诺塔,阶乘问题，迷宫问题,球和篮子的问题(google编程大赛)
• 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等。
• 将用栈解决的问题–>递归代码比较简洁

7.4.3 递归举例

【打印问题】

/**
 * ClassName: T
 * date: 2022/9/2 16:23
 *
 * @author DingJiaxiong
 */

class T {
    public void test(int n){
        if (n > 2){
            test(n - 1);
        }
        System.out.println("n = " + n);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/**
 * ClassName: Recursion01
 * date: 2022/9/2 16:22
 *
 * @author DingJiaxiong
 */

public class Recursion01 {
    public static void main(String[] args) {
        T t1 = new T();
        t1.test(4);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

运行结果

这很好理解

初始进入方法 n =4 ，n > 2成立，立马执行test(3)

n = 3，n > 2成立，立马执行 test(2)，

n = 2，n > 2不成立，输出2

输出3

输出4

【阶乘问题】

public int factorial(int n){
    if (n == 1){
        return 1;
    }
    else{
        return factorial(n - 1) * n;
   }
}
1
2
3
4
5
6
7
8

调用结果

调用过程

韩老师的图解：

7.4.4 递归重要规则

• 执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
• 方法的局部变量是独立的,不会相互影响,比如n变量
• 如果方法中使用的是引用类型变量(比如数组，对象),就会共享该引用类型的数据.
• 递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError)
• 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁,同时当方法执行完毕或者返回时，该方法也就执行完毕。

7.4.5 课堂作业

1. 请使用递归的方式求出斐波那契数1,1,2.3.5,8,13.….给你一个整数n，求出它的值是多少
2. 猴子吃桃子问题:有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个!以后每天猴子都吃其中的一半，然后再多吃一个。当到第10天时,想再吃时(即还没吃)，发现只有1个桃子了。问题:最初共多少个桃子?

经典斐波那契：

public int fibonacci(int n){
    if (n >= 1){
        if (n == 1 || n == 2){
            return 1;
        }
        else{
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
    else{
        System.out.println("要求输入的n >= 1的整数");
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

调用

/**
 * ClassName: RecursionExercise01
 * date: 2022/9/2 16:35
 *
 * @author DingJiaxiong
 */

public class RecursionExercise01 {
    public static void main(String[] args) {
        T t1 = new T();
        int n = 7;
        System.out.println("n=" + n + "时，对应的斐波那契数 = " + t1.fibonacci(n));
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

运行结果

桃子问题：

/**
 * ClassName: T
 * date: 2022/9/2 16:23
 *
 * @author DingJiaxiong
 */

class T {
    public void test(int n) {
        if (n > 2) {
            test(n - 1);
        }
        System.out.println("n = " + n);
    }


    public int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return factorial(n - 1) * n;
        }
    }

    public int fibonacci(int n) {
        if (n >= 1) {
            if (n == 1 || n == 2) {
                return 1;
            } else {
                return fibonacci(n - 1) + fibonacci(n - 2);
            }
        } else {
            System.out.println("要求输入的n >= 1的整数");
            return -1;
        }
    }

    public int peach(int day) {
        if (day == 10) {
            return 1;
        } else if (day >= 1 && day <= 9) {
            return ((peach(day + 1) + 1) * 2);
        } else {
            System.out.println("day应该是1-10");
            return -1;
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

调用类

/**
 * ClassName: RecursionExercise01
 * date: 2022/9/2 16:35
 *
 * @author DingJiaxiong
 */

public class RecursionExercise01 {
    public static void main(String[] args) {
        T t1 = new T();
        int n = 7;
//        System.out\.println("n=" + n + "时，对应的斐波那契数 = " + t1.fibonacci(n));

        int day = 9;
        int peachNum = t1.peach(day);

        if (peachNum != -1){
            System.out.println("第" + day + "天有" + peachNum + "个桃子");
        }

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行结果