好玩的网站列表

1.如何理解递归

• 递
  • 去的过程
• 归
  • 回来的过程

给我的感觉是先努力去溯源，拿到源数据以后就相当于多了一个信息，然后再依托多了一个的信息，来解决问题。

f(n) = f(n-1) + 1 

2. 递归的条件

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

3. 如何写递归代码

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

E.G

n个台阶，每次可以跨过1个或者2个，问一共多少种走法？

• 可以划分为子问题，即一共的走法等于我先走一步，剩下的n-1共同的走法和先走两步，剩下的n-1共同的走法的和。就有了一个递归公式：

f(n) = f(n-1) + f(n-2)

终止条件，看最后几个corner case，只有一个台阶，只有两个台阶，然后用3，4来验证一下。

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

不要人为加大难度，遇到递归，抽象成一个递推公式，不再一层层的想其调用关系，不要试图用人脑去分解递归的步骤

分解子问题的时候，当我们将其分解成几个子问题B C D以后，我们要做的是在假设子问题 BCD都已经解决的前提下，思考如何解决问题A。这样子我们就可以思考问题A和子问题B,C,D两层之间的关系就可以了，不需要再一层一层往下思考更深的子问题之间的关系了。屏蔽掉递归的实现细节，我们理解起来就会容易很多了

4. 警惕堆栈溢出

• 递归容易堆栈溢出
• 函数调用会使用栈来保存临时变量，每调用一个函数，都会将临时变量封装为栈帧压入内存栈当中。等函数执行完成返回时，才出栈。
• 系统栈或者虚拟机栈空间都不大，如果递归层很多的话，那么就会有堆栈溢出的风险。
• 可以在代码中限制递归调用的最大深度来解决这个问题

递归好处是表达能力强，很容易去理顺其想要表达的内容；坏处是空间复杂度会比较高，因为每次递归的时候都需要在内存栈中保存一次现场数据，所以在分析递归代码空间复杂度的时候，是需要额外考虑这部分的开销的。

5. 重复计算问题

子步骤会被计算了很多很多遍，为了避免这种重复计算，可以使用一些数据结构来保存已经求解过得f(k)。当递归调用到f(k)的时候，先看下是否已经求解过了

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 stone2paul@gmail.com