递归调用函数导致的栈溢出

栈溢出

程序中的函数调用是通过栈实现的。每一次函数执行，都会把方法压到执行栈中，方法调用结束后就会弹出该栈帧。

栈的大小是有限的，递归调用次数过多的话就会导致栈溢出，触发(js)Maximum call stack size exceeded异常，程序崩溃

// 溢出示例
(function getStackDepth(){
  try {
    // let obj = {} // 新声明的变量会占用栈空间
    return 1 + getStackDepth()
  } catch (e) {
    return 1 // Call stack overflow
  }
})()
11411 // chrome 结果
// 数量取决于方法体所占用的空间，占用空间越大，可用栈数量越小。可尝试在方法中增加变量，会发现结果变小。

优化

使用循环替代递归(大部分递归都可以用循环实现)

尾递归：指在方法返回时只调用本身，且不能包含表达式。编译器或解释器会把尾递归做优化，使递归方法不论调用多少次，都只占用一个栈帧，所以不会出现栈溢出。【Java没有尾递归优化】

// 用递归实现总和
const sum = (n) => {
  if (n <= 1) return n
  return n + sum(n-1) // 包含表达式，非尾递归
}
sum(10) // 10
sum(100000) // 爆栈 VM505:2 Uncaught RangeError: Maximum call stack size exceeded

// 尾递归实现
const sum = (n, prevSum = 0) => {
  if (n <= 1) return n + prevSum;
  return sum(n-1, n + prevSum) // return时调用本身
}

// 循环实现
function sum(num){
  let res = 0
  while(num--){
    res += num + 1
  }
  return res
}
sum(100000) // 正常输出 5000050000

递归调用函数导致的栈溢出 ​

栈溢出 ​

优化 ​

递归调用函数导致的栈溢出

栈溢出

优化