JavaScript代码出现栈溢出之尾调用优化

作者: tww844475003 分类: 前端开发 发布时间: 2022-03-12 18:51

说栈溢出之前,我们先来一起学习下调用栈,为什么了

什么是 javascript 调用栈

javascript 引擎是利用栈的这种数据结构来管理执行上下文的。在执行上下文创建好后,javascript 引擎会将执行上下文数据压入栈中,通常把这种用来管理执行上下文件的栈称为执行上下文栈,又称调用栈

  • 可以帮助了解 javascript 引擎的工作原理
  • 更好的调试 javascript

比如你在开发代码时,有时候可能会遇到栈溢出的错误,如下图所示:

function runStack(n, result) {
  if (n === 0) return result;
  return runStack(n - 2, result);
}
runStack(50000, 100)

为什么会出现这种错误呢?这就涉及到了调用栈的内容,在 javascript 编程中,经常会出现在一个函数中调用另外一个函数的情况,调用栈就是用来管理函数调用关系的一种数据结构。

首先来说说什么栈结构:

栈结构,可以结合一个贴切的例子来理解,一条单车道的单行线,一端被堵住了,而另一端入口处没有任何提示信息,堵住之后就只能后进去的车子先出来,这时堵住的单行线就可以看作一个栈容器,车子开时单行线叫做入栈,车子倒出去叫做出栈。

在车流量较大的场景中,就会发生反复的入栈、栈满、出栈、空栈和再次入栈,一直循环。

同理栈满了就会出栈溢出,上面提到的错误。

在开发中,如何利用好调用栈

  • 如何利用浏览器查看调用栈的信息

当执行一段复杂的代码时,可能很难从代码文件中分析其调用关系,这时候就可心在需要查看的函数中加入断点,然后执行到该函数,就可以查看该函数的调用栈了。

这里我们拿上面那段代码做个演示,打开“开发者工具”=》“source”,选择 javascript 代码,加上断点,刷新页面。就可以看到 runStack 函数时,执行流程就暂停了,这时可以通过右边的 “call stack“ 来查看当前的调用栈情况,如下图:

从图中可以看出,右边的 “call stack” 下面显示出来了函数的调用关系

栈的最底部是 anonymous,也就是全局的函数入口

中间的 runStack 函数随代码的执行,栈越来越大,就会造成溢出

除了通过断点来查看调用栈,也可以使用 console.trace() 来输出当前函数的调用关系。

尾调用优化

尾调用是函数式编程的一个重要概念,本身非常简单。就是:某个函数的最后一步是调用另一个函数

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

注意:只有不再用到外层函数的内部变量,内层函数的调用帧才会取代外层函数的调用帧,否则无法进行”尾调用优化

function animal(des) {
  var name = 'Dog';
  function run(data) {
    return name + data;
  }
  return run(des)
}

因为内层函数 run 用到了外层函数 animal 的内部变量 name。

  • 目前自会有Safari浏览器支持尾调用优化,Chrome和Fiefox都不支持
  • ES6的尾调用优化只在严格模式下开启,正常模式下是无效的(因为在正常模式下,函数内部有两个变量,可以跟踪函数的调用栈)
    • func.arguments:返回调用时函数的参数
    • func.caller:返回调用当前函数的那个函数
    • 尾调用优化发生时,函数的调用栈会改写,因此上面两个变量就会失真。严格模式下禁用了这两个变量,所以尾调用优化仅在严格模式下生效

尾递归

  • 示例:计算阶乘
// 非尾调用 (计算n的阶乘,最多需要保存n个调用记录,复杂度O(n))
function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}
// 尾调用 (只保留一个调用记录,复杂度O(1))
function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

尾递归优化实现

尾递归优化只能在严格模式下生效,正常情况下,或者那些不支持该功能的环境中,可以自己实现尾递归优化

思路:尾递归之所以需要优化,原因是调用栈太多,造成溢出,那么只要减少调用栈,也就不会溢出了。如何减少调用栈?使用”循环“代替递归

蹦床函数(trampoline)可以将递归执行转为循环执行。

function trampoline(f) {
  while(f && f instanceof Function) {
    f = f();
  }
  return f;
}
function runStack(n) {
  if (n === 0) return 100;
  return runStack.bind(null, n - 2);
}
trampoline(runStack(50000))

蹦床函数接收到个函数 f 做为参数,只要 f 执行后,返回一个函数就继续执行。注意,这里是执行返回的函数,而不是函数里边调用函数,这样就避免了递归执行,从而消除了调用栈过大的问题。

蹦床函数其实并不是真正的尾递归优化:

function tco(f) {
  var value;
  var active = false;
  var accumulated = [];

  return function accumulator() {
    accumulated.push(arguments);
    if (!active) {
      active = true;
      while (accumulated.length) {
        value = f.apply(this, accumulated.shift());
      }
      active = false;
      return value;
    }
  }
}
var runStack = tco(function(n) {
  if (n === 0) return 100;
  return runStack(n - 2)
})
console.log(runStack(50000))
前端开发那点事
微信公众号搜索“前端开发那点事”

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表回复

您的电子邮箱地址不会被公开。