编程小贴士

给你的编程提供小点子


Javascript中递归造成的堆栈溢出及解决方案

关于堆栈的溢出问题,在Javascript日常开发中很常见,Google了下,相关问题还是比较多的。本文旨在描述如何解决此类问题。 首先看一个实例(当然你可以使用更容易的方式实现,这里我们仅探讨递归):

 

  1. function isEven (num) {
  2.     if (num === 0) {
  3.         return true;
  4.     }
  5.     if (num === 1) {
  6.         return false;
  7.     }
  8.     return isEven(Math.abs(num) – 2);
  9. }
  10. //Outputs: true
  11. console.log(isEven(10));
  12. //Outputs: false
  13. console.log(isEven(9));

 

当我们把参数改成10000时,运行下例会发生堆栈溢出:

 

  1. function isEven (num) {
  2.     if (num === 0) {
  3.         return true;
  4.     }
  5.     if (num === 1) {
  6.         return false;
  7.     }
  8.     return isEven(Math.abs(num) – 2);
  9. }
  10. //不同的javascript引擎报错可能不同
  11. //Outputs: Uncaught RangeError: Maximum call stack size exceeded
  12. console.log(isEven(10000));

 

原因是每次执行代码时,都会分配一定尺寸的栈空间(Windows系统中为1M),每次方法调用时都会在栈里储存一定信息(如参数、局部变量、返回值等等),这些信息再少也会占用一定空间,成千上万个此类空间累积起来,自然就超过线程的栈空间了。那么如何解决此类问题?

使用闭包:

 

  1. function isEven (num) {
  2.     if (num === 0) {
  3.         return true;
  4.     }
  5.     if (num === 1) {
  6.         return false;
  7.     }
  8.     return function() {
  9.         return isEven(Math.abs(num) – 2);
  10.     }
  11. }
  12. //Outputs: true
  13. console.log(isEven(4)()());

 

此时每次调用时,返回一个匿名函数,匿名函数执行相关的参数和局部变量将会释放,不会额外增加堆栈大小。

优化调用:

上例调用比较麻烦,优化如下:

 

  1. function isEven (num) {
  2.     if (num === 0) {
  3.         return true;
  4.     }
  5.     if (num === 1) {
  6.         return false;
  7.     }
  8.     return function() {
  9.         return isEven(Math.abs(num) – 2);
  10.     }
  11. }
  12. function trampoline (func, arg) {
  13.     var value = func(arg);
  14.     while(typeof value === “function”) {
  15.         value = value();
  16.     }
  17.     return value;
  18. }
  19. //Outputs: true
  20. console.log(trampoline(isEven, 10000));
  21. //Outputs: false
  22. console.log(trampoline(isEven, 10001));

现在我们可以解决堆栈溢出问题了,但是不是感觉每次tarmpoline(isEven, 1000)这种调用方式不是很好,我们可以使用bind来绑定:

  1. function isEven(n) {
  2.     /**
  3.      * [isEvenInner 递归]
  4.      * @param  {[type]}  num [description]
  5.      * @return {Boolean}     [description]
  6.      */
  7.     function isEvenInner (n) {
  8.         if (n === 0) {
  9.             return true;
  10.         }
  11.         if (n === 1) {
  12.             return false;
  13.         }
  14.         return function() {
  15.             return isEvenInner(Math.abs(n) – 2);
  16.         }
  17.     }
  18.     /**
  19.      * [trampoline 迭代]
  20.      * @param  {[type]} func [description]
  21.      * @param  {[type]} arg  [description]
  22.      * @return {[type]}      [description]
  23.      */
  24.     function trampoline (func, arg) {
  25.         var value = func(arg);
  26.         while(typeof value === “function”) {
  27.             value = value();
  28.         }
  29.         return value;
  30.     }
  31.     return trampoline.bind(null, isEvenInner)(n);
  32. }
  33. //Outputs: true
  34. console.log(isEven(10000));
  35. //Outputs: false
  36. console.log(isEven(10001));


虽然上例实现了我们想要的效果,但是trampoline函数还是有一定的局限性:


1.假设你只传递一个参数给递归函数


value = func(arg); 修改为 value = func.apply(func, arg);


2.假设最后的返回值不是一个函数 关于更健壮性的实现,请看underscore-contrib中源码。

转自Benjamin-专注前端开发和用户体验

129 Responses to “ Javascript中递归造成的堆栈溢出及解决方案 ”

  1. suba suba说道:

    hJhMzL This is a topic which is near to my heart Many thanks! Where are your contact details though?

  2. time and actual effort to produce a good article but what can I say I procrastinate a

  3. Kickboxing说道:

    Many thanks for sharing this excellent post. Very inspiring! (as always, btw)

  4. girl coloring说道:

    This is very interesting, You are a very skilled blogger. I ave joined your rss feed and look forward to seeking more of your magnificent post. Also, I have shared your website in my social networks!

  5. It as hard to find well-informed people on this subject, but you sound like you know what you are talking about! Thanks

  6. Thanks so much for the article. Keep writing.

  7. montaj krovli说道:

    Major thanks for the article post.Really looking forward to read more. Much obliged.

  8. may dong phuc说道:

    This site was how do I say it? Relevant!! Finally I have found something that helped me. Thanks!

  9. Im obliged for the blog post.Really looking forward to read more. Really Cool.

  10. Click to read说道:

    Looking forward to reading more. Great blog article. Will read on…

  11. a fantastic read说道:

    There as certainly a lot to learn about this topic. I love all the points you have made.

  12. click here说道:

    Way cool! Some very valid points! I appreciate you writing this write-up and the rest of the site is also very good.

  13. I was suggested this blog by my cousin. I am not sure whether this post is written by him as no one else know such detailed about my problem. You are amazing! Thanks!

  14. online说道:

    wow, awesome article post.Thanks Again. Want more.

  15. Really appreciate you sharing this post. Cool.

  16. visit website说道:

    You, my pal, ROCK! I found exactly the info I already searched everywhere and simply could not find it. What a perfect web site.

  17. Woking taxi说道:

    Thanks for sharing, this is a fantastic post.Really looking forward to read more. Cool.

  18. bitstarz review说道:

    some fastidious points here. Any way keep up wrinting.

  19. Really good information can be found on site.

  20. Wohh just what I was searching for, regards for putting up.

  21. status online说道:

    I was suggested this website by my cousin. I am not sure whether this post is written by him as no one else know such detailed about my trouble. You are wonderful! Thanks!

  22. The Lost Ways说道:

    Very nice post. I just stumbled upon your weblog and wished to say that I have truly enjoyed browsing your blog posts. After all I will be subscribing to your feed and I hope you write again soon!

  23. Im grateful for the blog.Thanks Again. Much obliged.

  24. Lovely just what I was looking for.Thanks to the author for taking his time on this one.

  25. Share说道:

    Wow, great article.Really thank you! Want more.

  26. Very good information. Lucky me I came across your website by chance (stumbleupon). I ave saved as a favorite for later!

  27. Continued说道:

    It will put the value he invested in the house at risk to offer into through the roof

  28. Nwokolo说道:

    Keep up the good work i will return often.

  29. Say, you got a nice blog post.Really looking forward to read more. Fantastic.

  30. klm voucher说道:

    Keep up the fantastic piece of work, I read few blog posts on this web site and I believe that your site is real interesting and has lots of great information.

  31. Secure Document Storage Advantages | West Coast Archives

  32. ebay voucher说道:

    Thanks for sharing, this is a fantastic post.Much thanks again. Want more.

  33. That is a great tip particularly to those fresh to the blogosphere. Short but very precise information Thank you for sharing this one. A must read article!

  34. metal recycling说道:

    What as up colleagues, I am for a second time at this place, and reading this post related to Search engine optimization, its also a nice article, therefore keep it up.

  35. Looking around While I was browsing yesterday I noticed a great post about

  36. modified by way of flipping armrests. With these ensembles, you could transform a few

  37. Wow! This could be one particular of the most beneficial blogs We ave ever arrive across on this subject. Basically Magnificent. I am also an expert in this topic so I can understand your effort.

  38. Looking forward to reading more. Great post.Really looking forward to read more. Cool.

  39. Tra thao moc说道:

    This is my first time pay a quick visit at here and i am really pleassant to read everthing at one place.

  40. casino betting说道:

    There may be noticeably a bundle to learn about this. I assume you made certain nice points in options also.

  41. That is a very good tip especially to those fresh to the blogosphere. Brief but very precise information Thank you for sharing this one. A must read post!

  42. Your style is so unique compared to other people I ave read stuff from. I appreciate you for posting when you have the opportunity, Guess I will just book mark this web site.

  43. That is a good tip particularly to those new to the blogosphere. Simple but very accurate info Thank you for sharing this one. A must read article!

  44. Perfectly written content material, Really enjoyed reading through.

  45. This blog is obviously entertaining additionally factual. I have picked a bunch of interesting tips out of this amazing blog. I ad love to return again soon. Thanks a bunch!

  46. Miracle Ndu说道:

    It as hard to find educated people on this topic, but you sound like you know what you are talking about! Thanks

  47. Elena Matei说道:

    Thanks for the blog article.Much thanks again. Fantastic.

  48. click here说道:

    It cаА аЂаn bаА аЂа• seeen and ju?ged only by watching the

  49. medical podcasts说道:

    Thanks a lot for the blog. Keep writing.

  50. share说道:

    I will immediately grasp your rss feed as I can at to find your e-mail subscription hyperlink or newsletter service. Do you have any? Kindly allow me know in order that I may just subscribe. Thanks.

  51. women说道:

    I’а†ve not too long ago started a weblog, the info you supply on this site has helped me considerably. Thanks for all your time & perform.

  52. Very nice blog post. I certainly love this site. Continue the good work!

  53. Hosting说道:

    Thanks again for the article.Really looking forward to read more. Want more.

  54. This page certainly has all of the information I needed concerning this subject and didn at know who to ask.

  55. I think this is a real great article post. Awesome.

  56. I Will have to visit again when my course load lets up аАа’аАТ‚б‚Т€Т nonetheless I am taking your Rss feed so i could read your web blog offline. Thanks.

  57. Crochet bolero说道:

    Really enjoyed this post.Really thank you! Fantastic.

  58. Sisimiut说道:

    Thanks for sharing, this is a fantastic blog post.Thanks Again. Want more.

  59. online说道:

    Wow, great blog.Much thanks again. Much obliged.

  60. blue nike说道:

    Peculiar article, totally what I wanted to find.

  61. value说道:

    The longest way round is the shortest way home.

  62. I will right away grasp your rss as I can at in finding your email subscription hyperlink or newsletter service. Do you have any? Please allow me realize so that I may subscribe. Thanks.

  63. Keep up the good work , I read few blog posts on this web site and I conceive that your web blog is very interesting and has got sets of excellent info.

  64. School news说道:

    outlet went on to play the Angels in this ministry will

  65. Waec exam说道:

    Wow, great blog.Really looking forward to read more. Fantastic.

  66. Im thankful for the post.Thanks Again. Really Great.

  67. Thanks for sharing your info. I truly appreciate your efforts and I will be waiting for your further post thank you once again.

  68. Ridiculous quest there. What occurred after? Thanks!

  69. Real estate说道:

    Touche. Great arguments. Keep up the great effort.

  70. Thanks for sharing, this is a fantastic article post.Much thanks again. Really Cool.

  71. Open heaven说道:

    What is the best technique to search intended for blogs you are concerned in?

  72. Valuable info. Lucky me I found your website by accident, and I am shocked why this accident did not happened earlier! I bookmarked it.

  73. Im grateful for the blog.Really thank you! Fantastic.

  74. Would love to perpetually get updated outstanding web site!.

  75. Merely wanna tell that this is very beneficial , Thanks for taking your time to write this.

  76. not understanding anything completely, but

  77. Wow that was odd. I just wrote an incredibly long comment but after I clicked submit my comment didn at show up. Grrrr well I am not writing all that over again. Anyway, just wanted to say great blog!

  78. ventas说道:

    they all are tired from white teeth thats why they put gold or silver teeth!!!!

  79. ppi claims ireland I work for a small business and they don at have a website. What is the easiest, cheapest way to start a professional looking website?.

  80. MTN说道:

    Wow! This could be one particular of the most beneficial blogs We have ever arrive across on this subject. Basically Excellent. I am also a specialist in this topic so I can understand your hard work.

  81. hotel说道:

    Some truly select posts on this internet site , saved to favorites.

  82. Thanks for the article.Thanks Again. Fantastic.

  83. There as certainly a lot to learn about this issue. I really like all the points you ave made.

  84. Outstanding post, you have pointed out some great points, I too conceive this s a very great website.

  85. Nice blog here! Additionally your website loads up very fast! What web host are you the usage of? Can I get your associate link to your host? I want my website loaded up as fast as yours lol

  86. Impressive how pleasurable it is to read this blog.

  87. accident lawyer说道:

    Very good post. I definitely appreciate this site. Stick with it!

  88. Thank you for sharing this fine piece. Very inspiring! (as always, btw)

  89. too substantially vitamin-a may also lead to osteoporosis but aging could be the quantity cause of it`

  90. Really appreciate you sharing this article post.Thanks Again. Will read on

  91. Studying this information So i am happy to convey that

  92. dclm devotionals说道:

    Im obliged for the article. Will read on

  93. you can check说道:

    This is really interesting, You are a very skilled blogger. I ave joined your feed and look forward to seeking more of your magnificent post. Also, I ave shared your web site in my social networks!

  94. This particular blog is definitely entertaining and diverting. I have found a bunch of useful advices out of this amazing blog. I ad love to go back over and over again. Thanks a lot!

  95. I truly appreciate this post. I ave been looking all over for this! Thank goodness I found it on Bing. You have made my day! Thx again..

  96. cong ty luat说道:

    You made some clear points there. I looked on the internet for the topic and found most guys will consent with your website.

  97. click here说道:

    Of course, what a fantastic blog and educative posts, I surely will bookmark your site.Have an awsome day!

  98. like this说道:

    Thanks so much for the article post.Much thanks again. Will read on

  99. have a look at说道:

    This awesome blog is without a doubt educating and factual. I have chosen helluva helpful stuff out of it. I ad love to come back over and over again. Thanks a lot!

  100. pretty beneficial stuff, overall I feel this is really worth a bookmark, thanks

  101. Wow, superb blog layout! How long have you been blogging for? you made blogging look easy. The overall look of your site is excellent, as well as the content!

  102. Really informative blog article.Really thank you! Really Great.

  103. Outstanding post however I was wondering if you could write a litte more on this subject? I ad be very grateful if you could elaborate a little bit more. Appreciate it!

  104. I visited many sites except the audio quality for audio songs current at this web

  105. Typewriter.. or.. UROPYOURETER. meaning аАа’аАТ‚аЂТ˜a collection of urine and pus inside the ureter. a

  106. Share说道:

    You have made some good points there. I looked on the net for additional information about the issue and found most individuals will go along with your views on this site.

  107. wow, awesome blog post.Much thanks again. Keep writing.

  108. premium ads说道:

    It as going to be end of mine day, however before end I am reading this wonderful piece of writing to improve my know-how.

  109. Very nice post and right to the point. I am not sure if this is actually the best place to ask but do you folks have any thoughts on where to get some professional writers? Thx

  110. visit说道:

    This excellent website definitely has all of the info I needed about this subject and didn at know who to ask.

  111. explore说道:

    It as not that I want to duplicate your web site, but I really like the design. Could you let me know which style are you using? Or was it custom made?

  112. wow, awesome blog.Thanks Again. Awesome.

  113. Im grateful for the blog article.Thanks Again. Great.

  114. caratulas CD说道:

    Im obliged for the blog post.Much thanks again.

  115. go说道:

    Pretty nice post. I just stumbled upon your blog and wished to say that I ave truly enjoyed browsing your blog posts. After all I will be subscribing to your feed and I hope you write again soon!

  116. on your blog. Is this a paid theme or did you modify

  117. Kudos for the excellent piece of writing. I am glad I ave taken the time to read this.

  118. do说道:

    Wow, marvelous weblog structure! How lengthy have you been blogging for? you made running a blog glance easy. The total glance of your web site is great, let alone the content material!

  119. check here说道:

    It as hard to come by knowledgeable people in this particular topic, but you seem like you know what you are talking about! Thanks

  120. go there说道:

    shannonvine.com Shannon Vine Photography Blog

  121. Thanks again for the blog.Much thanks again.

  122. You will discover some interesting points in time in this article but I do not know if I see all of them center to heart.

  123. my portfolio说道:

    your posts more, pop! Your content is excellent but with pics and videos, this site could definitely be one of the best

  124. go here说道:

    This is certainly This is certainly a awesome write-up. Thanks for bothering to describe all of this out for us. It is a great help!

  125. sunday说道:

    Im grateful for the blog.Thanks Again. Awesome.

  126. latest song说道:

    Looking forward to reading more. Great article post.Thanks Again. Really Cool.

  127. calgary movers说道:

    Really appreciate you sharing this blog. Cool.

  128. What as up, just wanted to mention, I enjoyed this post. It was funny. Keep on posting!

  129. This awesome blog is definitely awesome and diverting. I have discovered helluva handy things out of this blog. I ad love to return over and over again. Thanks a lot!

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>