递归需要满足的三个条件

  • 一个问题的解可以分解为几个子问题的解
  • 这个问题与分解之后的子问题除了数据规模不同，求解思路完全一样

  • 存在递归终止条件

    如何编写递归代码

    写递归代码最关键的部分就是写出递推公式和找到终止条件。我们应该思考如何将大问题拆分成若干个类似的小问题，然后写出递归公式，再推敲递归的终止条件。编写递归代码的时候最重要的是把它抽象成一个递归公式，而不是用人脑去分解递归的每一步。

    递归代码要警惕堆栈溢出

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

    递归代码要警惕重复计算

    怎么将递归改写成非递归代码

    总结

    递归的优点：

  • 代码表达能力强

  • 代码简洁

递归写法存在很多问题：

  • 空间复杂度高
  • 存在堆栈溢出的风险
  • 存在重复计算

  • 过多的函数调用比较耗时

    小册练习

    电影院找座位

    递归写法

    1. function f(n) {
    2. if (n == 1) return 1;
    3. return f(n-1) + 1;
    4. }

    迭代写法

    1. function f(n) {
    2.   if (n == 1) return n;
    3.   let m = 1;
    5. for (let i = 2; i <=n ; i++) {
    6.     m = m + 1
    7. }
    8. return m;
    9. }

    爬楼梯问题

    递归写法

    1. function f(n) {
    2.   if (n == 0 || n == 1) return n;
    3. return f(n - 1) + f(n - 2)
    4. }

    迭代写法

    var numWays = function (n) {
  if (n == 0 || n == 1) return 1;
  let j = 1, k = 1, res = 0;
  for (let i = 2; i <= n; i++) {
      res = (j + k) % 1000000007;
      j = k;
      k = res;
  }
  return res;
};