很多语言都提供可尾递归优化，能将尾递归替换为循环方式调用，可以提高计算速度并避免堆栈溢出。但是javascript并没有提供递归优化，深度递归可能堆栈溢出，就需要自己手动写循环代码了。下面我们使用javascript写出计算斐波那契数列的例子。
1：递归调用
var fibonacci = function (n) {
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2)
}
这是递归方式，简单粗暴，时间复杂度为O(2^n)，空间复杂度为O(n)。
这种方式做了很多无畏的工作，因为一些值可能已经计算过了，而函数却重复计算了。我们可以把计算过的结果保存到一个数组中避免重复计算，这种方法称为“记忆(memoization)”。
2：递归+记忆
var fibonacci = function () {
var memo = [0, 1]
var fib = function (n) {
var result = memo[n]
if (typeof result !== 'number') {
result = fib(n - 1) + fib(n - 2)
memo[n] = result
}
return result
}
return fib
}()
fibonacci(10)//55
我们每次计算出结果后就把结果保存到memo数组中，每次计算之前都先从数组中查询是否存在计算过的值，有的话直接取出，否则再进行计算，这样节省了大量的计算。
我们可以写一个通用的函数：
var momizer = function (memo, formula) {
var recur = function (n) {
var result = memo[n]
if (typeof result !== 'number') {
result = formula(recur, n)
memo[n] = result
}
return result
}
return recur
}
var fibonacci = momizer([0, 1], function (recur, n) {
return recur(n - 1) + recur(n - 2)
})
var factorial = momizer([1, 1], function (recur, n) {
return n * recur(n - 1)
})
console.log(fibonacci(10))//55
console.log(factorial(4))//24
3：循环
function fb(n) {
var a, b, res;
a = 0;
b = 1;
for (var i = 2; i <= n; i++) {
res = a + b;
a = b;
b = res;
}
return res;
}
fb(10);//55
时间复杂度为O(n)，空间复杂度为O(1)。
循环比递归高效很多，并且避免堆栈溢出。
参考文献：
- JavaScript语言精粹第四章最后一节
- https://blog.csdn.net/a324539017/article/details/41799605
