递归也会导致内存溢出。涉及到递归的优化，尾递归。

尾调用：

某个函数的最后一步是调用另一个函数。

function fn(x){
    return g(x)
}
// 不是尾调用 
function fn(x){
    return g(x)+1
}

尾调用优化

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用帧，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用帧，取代外层函数的调用帧就可以了。即只保留内层函数的调用帧。

尾调用优化的意义

如果所有函数都是尾调用，那么完全可以做到每次执行时，调用帧只有一项，这将大大节省内存。

尾递归

如果尾调用自身，就是尾递归。

实例：

阶乘函数

// 非尾递归的写法 时间复杂度为O(n)
function factorial(n){
    if(n===1) return 1;
    return n*factorial(n-1)
}
factorial(5)

//尾递归的写法O(1)
function factorial(n,total){
    if(n===1) return total
    return factorial(n-1,n*total)
} 
factorial(5,1)

image.png

这里可以加debugger看到，用尾递归的时候，一直都用的Local这个作用域，或者说上下文，也或者说是调用帧，一直都是这一个。所以不会当数值变大的时候，超过最大内存值。

Fibonacci数列

// 非尾递归的写法 时间复杂度为O(n)
function fibonacci(n){
    if(n<=1) return 1;
    return fibonacci(n-1)+fibonacci(n-2)
}
Fibonacci(10) // 89 数值大会超时

// 尾递归的写法 
function fibonacci(n,result1 =1,result2=1){
    if(n<=1) return result2; 
    return fibonacci(n-1,result2,result1+result2)
}