去的过程叫“递”，回来的过程叫“归”

递归需要满足的三个条件

• 一个问题的解可以分解为一个或几个子问题的解
• 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
• 存在递归终止条件

如何编写递归代码

• 写出递推公式，找到终止条件

  ​ 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

• ==不要试图去分解递归的每个步骤==

  ​ 编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

==警惕堆栈溢出==

• 溢出原因

  ​ 函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。

  ​ 系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。

• 如何避免

  ​ 我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。

  ​ 但这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。

  ​ 所以，如果最大深度比较小，比如 10、50，就可以用这种方法，否则这种方法并不是很实用。

  ​ 最好的方法 是如果遇到深层次的递归调用，就将其转换成迭代来实现

==警惕重复计算==

​ 从图中，我们可以直观地看到，想要计算 f(5)，需要先计算 f(4) 和 f(3)，而计算 f(4) 还需要计算 f(3)，因此，f(3) 就被计算了很多次，这就是重复计算问题。

• 解决办法

  • 我们可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)

    ​ 当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免刚讲的问题了。

  • ==像这种避免重复计算的思想很重要==

递归代码改为非递归代码

• 递归优点

  • 代码的表达力很强，写起来简洁。

• 递归缺点

  • 容易造成堆栈溢出
  • 容易造成重复计算
  • 空间复杂度搞——因为递归调用一次就会在内存栈中保存一次现场数据
  • 时间复杂度较高——递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本

• 用迭代循环代替递归

  • 基本上所有的递归代码都可以借助迭代循环来实现