理解递归方法

- 日理万妓 2024-03-23 19:42 102阅读 0赞

## 递归相关问题 ##

> 1.  树和二叉树相关的大部分问题
> 2.  二分查找相关问题
> 3.  快速排序、归并排序相关问题
> 4.  所有回溯的问题
> 5.  所有动态规划的问题

## 本质与特征 ##

### 本质 ###

> 本质就是方法的调用，而且是方法自己调用自己。

### 特征 ###

> 1.  执行时范围不断缩小，这样才能触底反弹
> 2.  终止（结束）判断在调用递归的前面

#### 理解 ####

>  *  执行范围不断缩小

> 递归和数学中的递推差不多，设计递归就是寻找递推公式。
> 
> 例如：
> 
> 1. 阶乘的递推公式就是：f(n) = n \* f(n -1);
> 
> 2.斐波那契数列公式：f(n) = f(n-1) \* f(n-2);
> 
> 以上两个案例的n值都不断缩小
> 
> 除此之外，递归在树上缩小的体现如下：
> 
> int leftNode = traverse(leftNode.left);
> 
> int rightNode = traverse(rightNode.right);
> 
> 以上，每一次递归，都会将范围缩小到当前节点的左右孩子，接着继续缩小。

>  *  终止条件判断在递归调用的前面

> 递归之后可能还会有终止条件，但是 **在执行递归之前，一定会有一个终止条件。**

##### 错误示例 #####

> public void recursion(参数0)\{
> 
> recursion(参数1)
> 
> if(终止条件)\{
> 
> ......
> 
> \}
> 
> \}

> 上述代码会导致recursion()不断地自己调用自己，一直无法执行if中的语句，直到抛出栈溢出异常（StackOverflowError）

##### 正确示例 #####

> public void recursion(参数0)\{
> 
> if(终止条件)\{  
> ....
> 
> \}
> 
> recursion(参数1)
> 
> // 可能有逻辑运算
> 
> recursion(参数2)
> 
> ......
> 
> \}

> 因此，任何递归方法在执行之前，一定会有一个终止条件。

## 写递归方法 ##

#### 步骤 ####

> 1.  从小到大递推
> 2.  分情况讨论，明确结束条件
> 3.  组合出完整方法

##### 解释 #####

**从小到大递推**

> 先选几个较小的值验一下，再选择几个比较大的值，验一下即可。大部分从n = 1 ， 2， 3 或者只有一两个元素开始写最简单。
> 
> 例如斐波那契数列为：1 1 2 3 5 8 13 21....
> 
> 从第n=3开始就满足f(n) = f(n-1) \* f(n -2)这样的规律,然后再选几个数进行验证。
> 
> 最终发现 f(n) = f(n-1) \* f(n -2)就是我们需要的递归公式

##### 分情况讨论，明确结束条件 #####

> 因为递归方法里终止条件一定是靠前的，而大部分递归的终止条件不过是n最小开始触底反弹时的几种情况。
> 
> 例如：
> 
> 对于阶乘，当n = 1 时，就知道 f(1) = 1,因此就可写出阶乘的终止条件，如下：
> 
> int f(int n)\{
> 
> if(n == 1)\{
> 
> retrun 1;
> 
> \}
> 
> \}

> 有时候需要考虑的终止条件不止一个，例如斐波那契数列的递推公式 f(n) = f(n-1) \* f(n -2)里面，当n = 2 时，会出现 f(2) = f(1) + f(0),但是并没有f(0)这一项，因此，还需要限制n == 2.所以，其终止条件如下：
> 
> int f(int n)\{
> 
> if(n <= 2)\{
> 
> retrun 1;
> 
> \}
> 
> \}

> 通过以上案例可知，终止条件就是达到某种要就就要停下递归的条件，最直接的方式就是将特殊的案例给列出来，就像枚举一样，然后逐步优化。只有枚举清楚了，才可能设计出完整的终止条件。

#### 组合出完整方法 ####

> 将递归公式 和 终止条件 组合起来就变成了完整的方法。继续上述的两个例子为例，组合成完整的方法如下：

##### n的阶乘 #####

int f(int n){
        // 终止条件 
        if(n == 1){
            return 1;
        }
        // 递归方法
        return f(n - 1) * f(n); 
    }

##### 斐波那契数列第n项的值 #####

public int fabonacci(int n){
        if(n <= 2){
            return 1;
        }
        return fabonacci(n-1) * fabonacci(n - 2);
    }

## 看懂递归方法 ##

> 递归方法的特征就是“不撞南墙不回头”，也就是不到终止条件就一直递归。

#### 举例 ####

> 阶乘的 递归方法为例，当n = 4 时，执行过程如下图：

![image.png][]