勿让你的调用栈原地爆炸
栏目: JavaScript · 发布时间: 5年前
内容简介:对于编程中的一些类型判定问题(尤其是数学问题)最优雅的解决方案是使用递归,因为递归可以直接把这个问题转变成一个有关于数学定义的问题。不幸的是,在 JavaScript 中使用递归,会让你遇到一些麻烦事。假定我们想定义一个递归,该递归函数用于告诉我们一个数字是否是偶数。(是的,确定一个数字是否是偶数,这里有很多方法,我们只是拿递归来探索一下)我们可能会这样写代码就像下面这样:
对于编程中的一些类型判定问题(尤其是数学问题)最优雅的解决方案是使用递归,因为递归可以直接把这个问题转变成一个有关于数学定义的问题。不幸的是,在 JavaScript 中使用递归,会让你遇到一些麻烦事。
假定我们想定义一个递归,该递归函数用于告诉我们一个数字是否是偶数。(是的,确定一个数字是否是偶数,这里有很多方法,我们只是拿递归来探索一下)我们可能会这样写代码就像下面这样:
function isEvenNaive (num) { if (num === 0) { return true; } if (num === 1) { return false; } return isEvenNaive(Math.abs(num) - 2); } isEvenNaive(10); // => true isEvenNaive(9); // => false
这代码看起来非常合理。但是如果我们把一个大数,比如 9999 传给上述递归,会发生什么情况呢?
isEvenNaive(99999); // => InternalError: too much recursion
具体出现哪种错误,这各不相同,取决于 JavaScript 引擎,不过像上面这样的大数字,最终会让你达到引擎调用堆栈的深度限制,并且会伴随有 堆栈溢出 。
调用栈 本质上是一个保存在内存中的列表,该列表包括了所有那些未被执行完的函数调用、与函数相关的变量以及与函数相关的信息。每次使用大于 1 的值来调用 isEvenNaive,它都会自己调用自己,在这过程中,不但会把信息添加到堆栈,而且还会消耗更多资源。
只有当我们最后遇到递归的终止条件 0 或者 1,递归才不会继续下去,接着是清空调用栈以及释放资源。没有递归深度的限制(或者 尾递归 ),一个深度递归可能会耗完电脑上的所有资源。
但是递归还是很用的。有没有办法可以让我们既可以写递归又不会出现栈溢出?事实证明,还真有。
function isEvenInner (num) { if (num === 0) { return true; } if (num === 1) { return false; } return function() { return isEvenInner(Math.abs(num) - 2); }; } isEvenInner(8); // => function() { // return isEvenInner(Math.abs(num) - 2); // }; isEvenInner(8)()()()(); // => true
首先你会注意到, isEvenInner
函数这次没有直接调用自己,而是返回一个匿名函数。这就意味着每次调用 isEvenInner
函数,该函数都会被立即 resolved 掉, 并且不会增加堆栈的大小 。这也就意味着我们需要一种方法,来自动调用递归过程中所返回的全部匿名函数。这也是 trampoline
出现的由来。
function trampoline (func, arg) { var value = func(arg); while(typeof value === "function") { value = value(); } return value; } trampoline(isEvenInner, 99999); // => false trampoline(isEvenInner, 99998); // => true
trampoline
函数能够有效地将递归算法转换成用 while
循环来执行。只要 isEvenInner
函数一直返回函数, trampoline
函数就能一直执行这些返回函数。当我们最后终于返回一个非函数的值, trampoline
函数会将结果返回出去。
现在我们可以避免调用栈原地爆炸,但是这样调用 trampoline(isEvenInner, 3)
还不够优雅。那让我们用 bind 来加点 ”料“ 。
var isEven = trampoline.bind(null, isEvenInner); isEven(99999); // => false
需要着重注意的是,虽说所阐述的原理具有普适性,但是 trampoline
函数使用起来,有一定的局限性。
typeof function
有关更健壮的实现,可以参考 underscore-contrib 。
我希望上面讲的这些可以帮助你更好地理解 JavaScript 中递归的工作原理。
有些人提到,他们对深入的主题感兴趣,所以我正在努力增加这样的内容。如果你有推荐的话题,只需要回复这封邮件。我喜欢你们能够给出你们的反馈。
扫码关注w3ctech微信公众号
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 如何在Kubernetes中实现容器原地升级 原 荐
- javascript – jQuery click让我回到页面顶部.但我想留在原地
- Oracle 中国研发裁员:部分员工拉横幅抗议,多家企业原地招聘人才;蚂蚁金服重磅开源 SQLFlow;腾...
- 直观讲解-RPC调用和HTTP调用的区别
- 调用链系列一:解读UAVStack中的调用链技术
- 调用链系列二:解读UAVStack中的调用链技术
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
数据挖掘导论
(美)Pang-Ning Tan、Michael Steinbach、Vipin Kumar / 机械工业出版社 / 2010-9 / 59.00元
本书全面介绍了数据挖掘的理论和方法,着重介绍如何用数据挖掘知识解决各种实际问题,涉及学科领域众多,适用面广。 书中涵盖5个主题:数据、分类、关联分析、聚类和异常检测。除异常检测外,每个主题都包含两章:前面一章讲述基本概念、代表性算法和评估技术,后面一章较深入地讨论高级概念和算法。目的是使读者在透彻地理解数据挖掘基础的同时,还能了解更多重要的高级主题。 本书特色 ·包含大量的图表、......一起来看看 《数据挖掘导论》 这本书的介绍吧!