学写提高性能的代码之流程控制-4

这是我参与8月更文挑战的第10天，活动详情查看： 8月更文挑战

前言

简单来说，递归就是在函数执行体内部调用自身的行为，这种方式有时可以让复杂的算法实现变得简单，如计算斐波那契数或阶乘。
但使用递归也有一些潜在的问题需要注意：比如缺少或不明确递归的终止条件会很容易造成用户界面的卡顿，同时由于递归是一种通过空间换时间的算法，其执行过程中会入栈保存大量的中间运算结果，它对内存的开销将与递归次数成正比，由于浏览器都会限制JavaScript的调用栈大小，超出限制递归执行便会失败。

使用迭代

任何递归函数都可以改写成迭代的循环形式，虽然循环会引入自身的一些性能问题，但相比于长时间执行的递归函数，其性能开销还是要小很多的。以归并排序为例：

// 递归方式实现归并排序
function merge(left, right){
  const result = []
  while(left.length > 0 && right.length > 0) {
    // 把最小的先取出来放到结果中
    if(left[0] < left[0]){
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  // 合并
  return result.concat(left).concat(right)
}

// 递归函数
function mergeSort(array){
  if(array.length == 1) return array
  // 计算数组中点
  const middle = Math.floor(array.length / 2)
  // 分割数组
  const left = array.slice(0, middle)
  const right = array.slice(middle)
  // 进行递归合并与排序
  return merge(mergeSort(left), mergeSort(right))
 }

可以看出这段归并排序中，mergeSort()函数会被频繁调用，对于包含n个元素的数组来说，mergeSort()函数会被调用2n-1次，随着所处理数组元素的增多，这对浏览器的调用栈是一个严峻的考验。改为迭代方式如下：

// 用迭代方式改写递归函数
function mergeSort(array){
  if(array.length == 1 ) return array
  const len = array.length
  const work = []
  for(let i = 0 ; i < len; i ++){
    work.push([array[i]])
  }
  // 确保总数组长度为偶数
  if(len & 1) work.push([])
  // 迭代两两归并
  for(let lim = len; lim > 1; lim = (lim+1)/2) {
    for(let j = 0,k = 0; k < lim; j += 1, k += 2){
      work[j] = merge(work[k], work[k+1])
    }
    // 数组长度为奇数时，补一个空数组
    if(lim & 1) work[j] = []
  }
  return work[0]
}

此处通过迭代实现的mergeSort()函数，其功能上与递归方式相同，虽然在执行时间闪过来看可能要慢一些，但它不会收到浏览器对JavaScript调用栈的限制。

避免重复工作

如果在递归过程中，前一次的计算结果能被后一次计算使用，那么缓存前一次的计算结果就能有效避免许多重复工作，这样就能带来很好的性能提升。比如递归经常会处理的阶乘操作如下：

// 计算n的阶乘
function factorial(n){
  if(n === 0) {
    return 1
  } else {
    return n * fatorial(n-1)
  }
}

当我们要计算多个数的阶乘(如2、3、4)时，如果分别计算这三个数的阶乘，则函数factorial()总共要被调用12次，其中在计算4的阶乘时，会把3的阶乘重新计算一遍，计算3的阶乘时又会把2的阶乘重新计算一遍，可以看出如果在计算4 的阶乘之前，将3的阶乘数缓存下来，那么在计算4的阶乘时，递归仅需要再执行一次。如此通过缓存阶乘计算结果，避免多余计算过程，原本12次的递归调用，可以减少到5次。
根据这样的诉求，提供一个有效利用缓存来减少不必要计算的解决方案：

// 利用缓存避免重复计算  
function memoize(func, cache){
  const cache = cache || {}
  return function(args){  
    if(!cache.hasOwnProperty(args)){
      cache[args]=func(args);  
    }
    return cache[args];  
  }
}

该方法利用函数闭包有效避免了类似计算多次阶乘时的重复操作，确保只有当一个计算在之前从未发生过时，才产生新的计算值，这样前面的阶乘函数便可改写为：

// 缓存结果的阶乘方案
const memorizeFactorial = memorize(factorial, {'0': 1, '1': 1})

这种方式也存在性能问题，比如函数闭包延长了局部变量的存活期，如果数据量过大又不能有效回收，则容易导致内存溢出。这种方案也只有在程序中有相同参数多次调用才会比较省时，所以综合而言，优化方案还需根据具体使用场景具体考虑。