05-java数据结构之递归的详细介绍与学习

1、递归的概念

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

2、递归需要遵守的重要规则

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

3、通过问题来理解递归

3.1、打印问题

执行过程：
传入参数4之后，首先执行if里面的条件，test(4-1)，输出语句没执行，然后又执行if，t(3-1)，输出语句没执行，再次执行if，t(2-1)，输出语句没执行，最后n=1，直接输出，再输出n=2，在输出n=3，最后输出n=4。就是先要输出n=1，其他的值才能继续输出。

public class RecursionTest {
    public static void main(String[] args) {
        // 通过打印问题，回顾递归思路
        test(4);
    }

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

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

3.2、阶乘问题

思路：假设n=3，求3的阶乘其实就是 1 * 2 * 3，当传入参数3的时候，先执行factorial(2)*3，但是factorial(2)不知道等于多少，所以return还不能执行，先去执行factorial(2)，可以得到factorial(2)=factorial(1)*2；但是factorial(1)又不知道，所以先求得factorial(1)的值，得到factorial(1)的值为1之后，就可以得到factorial(2)的值，得到factorial(2)的值之后，可以得到factorial(3)的值。

    public static int  factorial(int n){
        if(n==1){
            return 1;
        }else{
            // 要先知道factorial(n-1)的值，从factorial(1)开始反推
            return factorial(n-1)*n;
        }
    }
1
2
3
4
5
6
7
8

3.3、取球问题

在n个球中，任意取m个(不放回)，求有多少中不同的取法。

/**
 * @User: 老潘
 * @date 2022年10月20日10:44
 * 递归----取球操作
 * 对于递归问题来说，该题似乎没有突破口，那么就需要发挥想象。
 * 带入一组简单的数字，比如3个中取2个球，将所有可能的组合枚举出来，观察这些组合可以如何划分。比如abc三个球，有ab,ac,bc三种，可以想象n个球中取1个幸运球，那么要么取到该球，要么取不到。
 * 如果取到了这个特殊球, 则:f(n-1,m-1),总数总是要减1, 因为取到了特殊球, 所以m-1, 反之没有取到特殊球, 则 f(n-1,m) 总数还是减1, 但是m的值不变。此时，所有取法即为f(n-1,m-1)+f(n-1,m)
 */
public class quQiu {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        // n个球，每次取m个不放回
        System.out.println("输入n和m的值，并用空格隔开");
        int n=sc.nextInt();
        int m=sc.nextInt();
        int k=f(n,m);
        System.out.println(k);
    }

    public static int f(int n,int m){
        // 取不了
        if(n<m){
            return 0;
        }
        if(n==m){
            return 1;
        }
        if(m==0){ // 判断m是否取到最后了
            return 1;
        }
        return f(n-1,m-1)+f(n-1,m);
    }
}

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

3.4、两个串的最大公共子序列的长度

自己跟着步骤反推一下吧

public class MaxGongStr {
    public static void main(String[] args) {
        int length = getMaxStrLength("ask1", "bsk2ask3");
        System.out.println(length);
    }

    private static int  getMaxStrLength(String a, String b) {
        // 判断两个字符串中是否有空字符串
        if(a.length()==0||b.length()==0){
            return 0;
        }
        //
        if(a.charAt(0)==b.charAt(0)){
            // 如果等于就看下一个字符是否相等
            return getMaxStrLength(a.substring(1),b.substring(1))+1;
        }else{
            return Math.max(getMaxStrLength(a,b.substring(1)),getMaxStrLength(a.substring(1),b));
        }
    }
}

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