从栈溢出看JS的运行方式

比如现在需要实现一个从1加到n的递归函数。

递归

这很简单，大概可以这么写。

function sum(n) {
    if (n === 1) {
        return 1
    }

    return n + sum(n - 1)
}

sum(10) // => 55

这很不错，然而如果去给他传递一个比较大的数字场面就会很尴尬。

sum(1e5) // => Uncaught RangeError: Maximum call stack size exceeded

这通常被称之为栈溢出，根据平台不同溢出的上限不同，不过最终都会溢出，从1万多到5万不等，参考这里。

为什么

为什么会这样，大概都听说过JavaScript是单线程语言，他只能一次做一件事情，他只有一个Call Stack（调用栈）。

每次函数调用时，他会被压入栈，当他调用完毕后会从栈中移除。

比如调用上面的sum(10)的时候，栈大概会长这个样子。

[sum(10), sum(9), sum(8), ..., sum(1)]

此时栈中有10个函数，然后到达的边界条件，当参数是1时return 1，于是最后一个函数就执行完毕了，会被从栈中移除。

[sum(10), sum(9), sum(8), ..., sum(2)] // => sum(1)被移除了, 返回1

sum(2)等于2 + sum(1)，于是也能计算出答案，也会被移除。

随后所有的函数都会按照上面的规律一个个执行完毕一个个被移除，调用栈被清空，脚本执行完毕。

而如果传入的是一个特别大的数字，栈就会很大。

[sum(1e5), sum(1e5 - 1), ...] // => 放不下了

那么要如何解决这个问题呢。

使用迭代

上面递归的思路如果用纯代码写大概是这样。

function sum(n) {
    const stack = []

    while (n > 0) {
        stack.push(n--)
    }

    let result = 0
    while (stack.length) {
        result += stack.pop()
    }

    return result
}

因为没有涉及到函数调用所以自然不会影响到调用栈，不过都这么写了为什么不直接用循环累加，下一个。

使用任务队列

当然我们也听说过Event Loop，虽然JavaScript本身是单线程的，但是平台也可以同时处理其他任务，我们可以通过Web APIs，或者是Node.js平台提供的接口，去进行异步函数调用。

在调用异步接口的同时，传入一个Callback（回调函数），这样那个回调函数就会加入任务队列。

每当主调用栈中的内容全部执行完毕后，便会去任务队列中取得第一个任务。

如此往复，就形成了Event Loop，当然任务队列还细分为微任务和宏任务，不过这里先不讨论那些。

我们这里使用Promise来创建一个简单的队列。

function sum(n) {
    if (n === 1) {
        return Promise.resolve(1)
    }

    return Promise.resolve(n - 1).then(sum).then(result => result + n)
}

这里Promise.resolve(n - 1).then(sum)这段代码中的sum，因为是在一个Promise的then后面执行的，所以会被放入异步的任务队列里。

sum(1e5).then(console.log) // => 5000050000

这样执行内部的步骤看上去像这样。

1. stack: [sum(1e5)] - 第一个函数放入调用栈并执行
2. queue: [sum(1e5 - 1)] - 把回调函数放入任务队列
3. stack: [] - 执行完毕调用栈中的函数，并移除
4. stack: [sum(1e5 - 1)] - 从任务队列中取到第一个函数，放入调用栈并执行
5. queue: [sum(1e5 - 2)] - 将下一个回调函数放入任务队列
6. ...重复

这样相当于每次调用栈只执行了一次sum函数，利用任务队列的特性解决了栈溢出的问题。

尾调用优化

在es6严格模式下，如果某个函数的最后一步是调用另一个函数，则会形成尾调用，具体的优化原理可以参考阮一峰的文章。

可以把上述的递归函数换一个写法如下所示：

'use strict'

function sum(n, result = 0) {
    if (n === 1) return result + 1
    return sum(n - 1, result + n)
}

console.log(sum(1e5)) // => 5000050000

不过上述代码目前只有在Safari浏览器能正常运行，其他的浏览器以及Node.js并不支持（至少是默认情况下）。

参考

• 尾调用优化
• JavaScript 运行机制详解：再谈Event Loop
• JavaScript Event Loop And Call Stack Explained
• MDN - Concurrency model and the event loop
• 原文地址