这个递归如何优化？

Question

在做 LeetCode 62题 时第一直觉是下面这个递归，但是这个递归问题太大了，很容易栈溢出，能否优化？或是此题不宜用递归解，得转换成循环？

var uniquePaths = function(m, n) {
  if (m === 1 || n === 1) {
    return 1
  }
  return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)
};
uniquePaths(100, 100);

Answer 1

从我的仓库摘一个代码，应该可以解决你的问题。

var uniquePaths = function (m, n) {
  const dp = Array(n).fill(1);

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] = dp[j] + dp[j - 1];
    }
  }

  return dp[n - 1];
};

仓库地址： https://github.com/azl3979858...

Answer 2

递归导致的栈溢出，可以通过将函数柯里化，然后优化函数尾调用的方法来解决。
ES6 标准里，浏览器实现箭头函数的时候必须部署尾调用优化，那么，柯里化的箭头函数尾调用来完成递归，就不会导致栈溢出了，可以专心优化算法。