递归

参考极客时间

满足的三个条件

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

  3. 存在递归终止条件

    如何写递归代码

  4. 最关键的是写出递推公式

  5. 找到终止条件
  6. 剩下将递推公式转化为代码

住： 主要是递推公式，先例举几项，在找规律，最后总结递推公式

题目1：爬楼梯

  1. 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。参考
    1. var climbStairs = function(n) {
    2.  if(n === 1) return 1
    3.  if(n === 2) return 2
    4.  return climbStairs(n-1) + climbStairs(n-2)
    5. };
    6. climbStairs(2) // 2
    7. climbStairs(3) // 3

    性能优化

  • 添加边界条件
    • 重复计算
  • 我们可以通过一个数据结构（比如散列表）来保存已经求解过的值，当递归调用该值时，可以先去数据结构里看下是否已经求解过了，这样可以减少很多不必要的计算
  1. // 函数的记忆优化
  2. function memorize(fn){
  3.   var cache = {}
  4.   return function(){
  5.     // 定义一个独一无二的 key,来存value
  6.     var key = arguments.length + Array.prototype.join.call(arguments)
  7.     console.log('key', key)
  8.     if(cache[key]){
  9.       return cache[key]
  10.     }
  11.     cache[key] = fn.apply(this, arguments)
  12.     return cache[key]
  13.   }
  14. }
  16. const func = memorize(climbStairs)
  18. // 比如 n=30 时， 采用 memorize 执行时间明显降低

  • 将递归代码改写为非递归代码

    • 空间复杂度降低，执行时间也得到大幅度提升

      1. var climbStairs = function(n) {
      2. if(n === 1) return 1
      3. if(n === 2) return 2
      4. let res = 0
      5. let per = 2
      6. let prepre = 1
      7. for(let i =3; i <= n; i++) {
      8. res = per + prepre // 前两项和
      9. prepre = per // prepre 值 变成 per
      10. per = res // per 值变成 每次计算的结果
      11. }
      12. return res
      13. }

      题目2：子集

      给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
      解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。参考leetcode-78

      1. /**
      2. * @param {number[]} nums
      3. * @return {number[][]}
      4. */
      5. var subsets = function(nums) {
      6. // 递归选与不选的问题
      7. const ans = []
      8. const temp = []
      9. const n = nums.length
      10. const recur = (nums, i) => {
      11. // 边界
      12. if (i === n) {
      13.  ans.push([...temp])
      14.  return
      15. }
      16. // 不选 i, 下一个
      17. recur(nums, i + 1)
      19. // 选 i，下一个
      20. temp.push(nums[i])
      21. recur(nums, i + 1)
      22. // 还原现场
      23. temp.pop()
      24. }
      25. recur(nums, 0)
      26. return ans
      27. };

      题目2：组合

      给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
      你可以按 任何顺序 返回答案。
      示例：

      1. 输入：n = 4, k = 2
      2. 输出：
      3. [
      4. [2,4],
      5. [3,4],
      6. [2,3],
      7. [1,2],
      8. [1,3],
      9. [1,4],
      10. ]

      求解和子集思路一样，都是选与不选问题，只不过这里加了条件，要选几个

      1. /**
      2. * @param {number} n
      3. * @param {number} k
      4. * @return {number[][]}
      5. */
      6. var combine = function(n, k) {
      7. const ans = []
      8. const temp = []
      9. const recur = (i) => {
      10. // 这里可以使用剪枝处理
      11. // 1.temp 的值数量已经大于k
      12. // 2.temp 值得数量 + 剩余的数（n - i + 1）都不够k个
      13. // if (temp.length > k || temp.length + (n - i + 1) < k) return
      14. // 递归边界
      15. if (i === n + 1) { // n 本身也要
      16.  if (temp.length === k) {
      17.    ans.push([...temp])
      18.  }
      19.  return
      20. }
      21. // i不选
      22. recur(i + 1)
      24. // 选i
      25. temp.push(i)
      26. recur(i + 1)
      27. // 还原现场
      28. temp.pop()
      29. }
      30. recur(1)
      31. return ans
      32. };

      总结

  • 递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现