理解递归

[18888628835]

理解递归

递归是一种解决问题的方法，它从解决问题的各个小部分开始，直到解决最初的大问题。

递归的条件

递归有两个条件：

• 调用自身
• 找到基线条件，即一个不再递归调用的条件（停止点），防止无限调用自身

下面用例子来分析采用递归方法来实现数组求和，假设数组为[1,2,3,4,5,6]。

我们首先分析一下数组求和的过程：

• 公式为：nums[0]+...nums[length-1] = sum
• 通过公式推导出基线是 length-1，在此时递归结束
• 从 nums[0]开始，index 不断递增

所以我们可以写出下面的代码

// 递归实现数组求和
//递归求和的重点：1.找到最小问题，2.调用自身
function sum(nums) {
  function sum2(nums, len) {
    if (len === nums.length) {
      //这里就是基线条件
      return 0;
    }
    return nums[len] + sum2(nums, len + 1); //调用自身
  }
  return sum2(nums, 0);
}

我们在写递归时，比较难判别的是如何考量基线条件。

递归解决阶乘问题

下面我们尝试来做一个更经典的递归问题-阶乘

我们来看看如何计算一个数的阶乘。数n的阶乘，定义为n!，表示从1到n的整数的乘积。

分析一下：

我们从n开始，一直到 1 才停止，分解一下就是n*(n-1)*(n-1-1)*...1

也就是说基线条件为 1，而且我们要不停调用自身。调用自身的行为就是不断乘以比自己小一位的数。

所以代码可以这样写

// 递归解决阶乘问题
function factorial(n) {
  function factorial2(current) {
    if (current === 1) {
      return 1;
    } else {
      return current * factorial2(current - 1);
    }
  }
  return factorial2(n);
}

调用栈

入门了递归的两个小案例，现在我们来了解一下调用栈问题。既然叫栈，那么说明这个数据结构是后进先出的。

调用栈是什么呢？我们可以理解为当进入一个函数内部时，底层会自动产生一个调用栈，把当前的函数的调用给push进去，当产生递归时，也就是进入一个函数后又进入一个函数时，会把当前函数的调用堆叠到调用栈中。这是因为每个调用都可能依赖前一个调用的结果。

我们把上面的函数复制到浏览器中，并且在factorial内打一个断点来检查一下就可以看到调用栈的处理过程。

当第一次进入factorial函数时，此时还没有调用factorial2函数，左边的 call stack 上只显示一个函数，然后当我们点击step into next function 按钮时，就可以看到调用栈内又多了一个函数，说明此时已经压栈了。

如果一直点下去，随着 current 的逐步减少，可以看到 call stack一直在增加函数，直到 current 等于1之后，开始弹栈，call stack 内的函数逐渐从顶部开始弹出。

可以用下图表示执行栈的步骤

每个调用栈不可能无限扩展，在浏览器中，调用栈也有大小限制，如果超过了这个数量，那么就会出现栈过大的提示。

斐波那契数列

斐波那契数列是另一个可以用递归解决的问题。它是一个由0、1、1、2、3、5、8、13、21、34等数组成的序列。从第二个1开始（也就是第二位），每一个数都是前一位和前两位的总和。

已知当 n 为1或者0时都返回 n 自身，所以这就是自身的基线点。那么我们可以写出一个输入n 得出n 位是多少数值的函数

function fibonacci(n) {
  if (n === 0 || n === 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

记忆化斐波那契数列

所谓记忆化函数，就是在函数内部增加一个闭包来进行缓存。当我们调用fibonacci(5)时，可以画一张这样的图来查看执行过程。

可以看到fibonacci(3)被调用两次了，这就可以用到缓存来记录下这个结果。

function memorizeFibonacci(n) {
  let cache = [0, 1];
  function fibonacci(n) {
    if (n === 1 || n === 0) {
      return n;
    }
    if (cache[n]) {
      return cache[n];
    }
    let result = fibonacci(n - 1) + fibonacci(n - 2);
    cache[n] = result;
    return result;
  }
  return fibonacci(n);
}

使用缓存可以有效减少重复的计算，优化计算效率。

这里有一道 leecode 题目，就可以使用缓存以避免计算时间过长而导致做题失败。
剑指 Offer 10- I. 斐波那契数列