数据结构与算法之递归

╰半夏微凉° 2024-04-17 05:59 93阅读 0赞

## 简介 ##

**递归就是方法自己调用自己**，每次调用时传入不同的参数，递归有助于解决复杂的问题，同时也能使代码变得简洁。

## 递归调用机制 ##

有编程的基础的同学，应该知道递归的写法，下面我将使用两个小案例来分析递归的调用机制。

案例一 递归打印数字：

public static void main(String[] args) {
    
        testRecursion(5);
    }
    public static void testRecursion(int n) {
        if (n > 2) {
            testRecursion(n - 1);
        }
        System.out.println("n=" + n);
    }

输出结果：

n=2
    n=3
    n=4
    n=5

递归打印数字流程示意图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5fY2hhbmd5aW5n_size_16_color_FFFFFF_t_70]  
流程分析：

1.  当递归方法调用自己时，就会在栈中开辟一个独立的空间；
2.  每个空间的基本数据类型变量，是独立的，互不影响，如果变量是引用类型，则会指向同一个内存地址；
3.  递归调用时，直到方法执行完毕，或者遇到`return`语句，才会结束；
4.  上述案例，`main`方法调用`testRecursion`传入参数`n=5`，当`n`大于`2`时，会递归调用`testRecursion`。当递归到`n`不大于2时，会依次执行递归调用后面的语句，此处是`System.out.println("n=" + n)`。直到方法执行完毕。

案例二 递归计算阶乘：

public static void main(String[] args) {
    
        int factorial = factorial(3);
        System.out.println("factorial=" + factorial);
    }
    public static int factorial(int n) {
       if (n == 1) {
            return n;
        } else {
            return factorial((n - 1)) * n;
        }
    }

输出结果：

factorial=6

## 递归使用场景 ##

1.  可用于解决各种数学问题，例如：汉诺塔、阶乘、迷宫回溯等；
2.  应用到算法中，例如：快速排序、归并排序、二分查找、粉质算法等；
3.  遇到复杂的数据结构时，可使用递归，可使代码更简洁；

## 递归需要遵守的规则 ##

1.  执行一个方法时，就创建了一个新的，受保护的独立空间，也就是栈；
2.  方法的局部变量是独立的，不会相互受到影响，例如上面演示的案例所用到的参数`n`，只针对基本数据类型；
3.  如果方法中使用的是引用类型的变量，就会共享该引用类型的数据；
4.  递归方法必须要有退出的条件，否则就会出现无限递归，最终抛出`StackOverflowError`异常；
5.  当一个方法执行完毕，或者遇到`return`语句，就会返回结果，遵守谁调用就会将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕；

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5fY2hhbmd5aW5n_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/efdd7455af0f45a2ad6bf35dccd90ddc.png