前言

本文简单记录算法学习中， 递归优化的一些方法

尾调用

简单来说就说一个函数末尾返回另一个函数

function a() {
    ...
    return a()    // 这种就属于尾调用
}

function a() {
    ...
    return n+b()   // 这种不属于， 因为return 了其他计算式
}

尾调用优化

当尾调用的不依赖当前函数时就是尾调用优化，调用栈尽可能少。

function a(n) {
    ...
    function b(n) {
        return n+x
    }
    return b(n)

    // 这个是尾调用， 但不是尾调用优化。
    // 因为执行 return 时 a依然在调用栈中
}

尾调用优化例子

1. 保证是一个尾调用
2. 保证调用栈尽可能的,return 的函数无副作用

// 阶乘函数
function f1(n) {
  if (n === 1) return n;
  return n * f1(n - 1);
}

function f2(n, total) {
  if (n === 1) {
    return total;
  }
  return arguments.callee(n - 1, n * total);
}

// 斐波拉契函数
function fb1(n) {
  if (n <= 2) {
    return 1;
  }
  return arguments.callee(n - 2) + arguments.callee(n - 1);
}

function fb2(n, a1, a2) {
  if (n === 1) {
    return a2;
  }
  return arguments.callee(n - 1, a2, a1 + a2);
}

缓存值的方式优化

通过把函数中值缓存起来，加快速度，这种仅限于结果集固定的情况

function memoizer(fn, cache = {}) {
  return function(arg) {
    if (!(arg in cache)) {
      cache[arg] = fn(arg);
    }
    return cache[arg];
  };
}
let fac = memoizer(function(n) {
  if (n === 1) return n;
  return n * arguments.callce(n - 1);
});
fac(5);

尾调用转 栈 + 迭代的通用方案

阮一峰书中看到的方案，可以对任意尾调用进行优化, 只能尾调用形式的递归

function tco(fn) {
  var value;
  var active = false;
  var accumulated = [];
  return function() {
    accumulated.push(arguments);
    if (!active) {
      active = true;
      while (accumulated.length) {
        value = fn.apply(this, accumulated.shift());
      }
      active = false;
      return value;
    }
  };
}

缓存值优化方案

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

// 优化

function optimizeRecursion(fn) {
  var cache = {};
  return function() {
    var arg = Array.prototype.join.call(arguments, ".");
    if (arg in cache) {
      return cache[arg];
    }
    return (cache[arg] = fn.apply(this, arguments));
  };
}

斐波拉契数列 转迭代 动态规划

var climbStairs = function(n) {
  const dp = [];
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

递归时间复杂度和空间复杂度计算规则

递归次数和计算函数的时间的乘积

二叉树的最大深度

普通迭代方案

function maxDeep(node) {
  if (node === null) {
    return 0;
  }
  return Math.max(maxDeep(node.left), maxDeep(node.right)) + 1;
}

总结 二叉树数组的关系

1. 深度 log2 (length+1)
2. i 行第一个元素和最后一个: 第一个 2^i - 1 最后一个 2^(i+1) - 2 ， i 从 0 开始
3. i 行元素个数 2 ^ i
4. 左节点 2 * i + 1 右节点 2 * i + 2