# 数据结构（四）递归


# 递归

- 描述： 一种非常高效、简洁的编程技巧。函数调用自身的方式称为递归调用，调用成为递，返回称为归；
- 正确姿势：找到如何将大问题分解为小问题的规律，并基于此写出递推公式。然后再敲定终止条件，生成递归函数。

## 优缺点：

- 优点：代码简洁，表达力强
- 缺点： 空间复杂度高，有堆栈溢出风险、存在重复计算、过多函数调用会耗时较多等问题。

## 递归需要满足的三个条件：

- 一个人问题的解可以分解为几个子问题（数据规模更小的问题）的解；
- 这个问题与分解后的子问题，除了数据规模不同，求解思路完全一样；
- 存在递归终止条件：把问题分解为子问题，把子问题再分解为子子问题，一层层分解下去，这就需要一个终止条件，防止无限分解；

## 练习题：

假设有 n 个台阶，每次你可以跨一个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？
提示： 如果有 7 个台阶，你可以 2，2，2，1 这样子上去，也可以 1，2，1，2，1 这样子上去。

解： 我们可以根据 第一步 的走法把所有走法分为两类，

- 第一类是第一步走了 1 个台阶
- 第二类是第一步走了 2 个台阶
  所以，n 个台阶的走法 = 先走 1 个台阶后，n-1 个台阶的走法 + 先走 2 个台阶后，n-1 个台阶的走法。

得到求解公式： `f(n) = f(n-1) + f(n-2)`
找到终止条件： 当有一个台阶时，只有一个走法，结束递归，f(1) = 1；当有两个台阶时，有两个走法，结束递归，f(2）= 2；

通过求解公式和终止条件，可以得到一个递归函数求出所有走法的总数

```
const func = (num) => {
  if (n === 1) return 1;
  if (n === 2) return 2;
  return f(n-1) + f(n-2);
}
```

## 技巧

如果一个问题 A 可以分解为若干个子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。屏蔽掉递归细节，把它抽象成一个递推公式，不要想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

## 递归的问题：

- 要警惕堆栈溢出：函数调用会使用栈来保存临时变量每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈，系统栈和虚拟机栈空间一般都不大，如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。

  解决：尽可能的限制递归深度和运算的复杂度

- 要警惕重复计算：如果把上题的递归过程拆解，如下图：
  ![demo](recursion.webp)
  我们可以直观的看到，想要计算 f(5)，需要先计算 f(4)和 f(3)，而计算 f(4)同样需要计算 f(3)，因此，f(3)就被计算了很多次，这就是重复计算问题。

  解决：可以将求解过的 f(k)保存起来，当递归调用到 f(k)时先看下是否已经求解过了，是则直接取值返回。

  ```
  const returnList = {};
  const func = (num) => {
    if (n === 1) return 1;
    if (n === 2) return 2;
    if (returnList[n]) {
      return rerutnList[n]
    }
    const val = f(n-1) + f(n-2)
    returnList[n] = val;
    return val;
  }
  ```

- 要警惕无限递归问题：
  解决： 一定要保证终止条件是有效且合理的，