Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have read recently some articles (e.g. http://dailyjs.com/2012/09/14/functional-programming/) about the functional aspects of Javascript and the relationship between Scheme and Javascript (the latter was influenced by the first, which is a functional language, while the O-O aspects are inherited from Self which is a prototyping-based language).

However my question is more specific: I was wondering if there are metrics about the performance of recursion vs. iteration in Javascript.

I know that in some languages (where by design iteration performs better) the difference is minimal because the interpreter / compiler converts recursion into iteration, however I guess that probably this is not the case of Javascript since it is, at least partially, a functional language.

share
3  
Make your own test and find out right away at jsperf.com –  TehShrike Dec 18 '12 at 16:44
    
Thanks for the link, it is very useful. I'll try. –  mastazi Dec 19 '12 at 3:37

4 Answers 4

up vote 13 down vote accepted

JavaScript does not perform tail recursion optimization, so if your recursion is too deep, you may get a call stack overflow. Iteration doesn't have such issues. If you think you are going to recurse too much, and you really need recursion (for example, to do flood-fill), replace the recursion with your own stack.

Recursion performance is probably worse than iteration performance, because function calls and returns require state preservation and restoration, while iteration simply jumps to another point in a function.

share
2  
Thanks for the link and the info, it is interesting –  mastazi Dec 18 '12 at 12:31
    
Just wondering... I've seen a bit of code where an empty array is created and the recursive function site is assigned to a position into the array and then the value stored into the array is returned. Is that what you mean by "replace the recursion with your own stack"? E.g.: var stack = []; var factorial = function(n) { if(n === 0) { return 1 } else { stack[n-1] = n * factorial(n - 1); return stack[n-1]; } } –  mastazi Dec 30 '12 at 9:07
    
@mastazi: No, this will make a useless call stack along with the internal one. I meant something like the queue-based flood-fill from Wikipedia. –  SiPlus Jan 6 '13 at 17:37
    
Thank you for the explanation and the link –  mastazi Jan 7 '13 at 2:39
1  
@mastazi Replace the else in that function with else if (stack[n-1]) { return stack[n-1]; } else and you have memoization. Whoever wrote that factorial code had an incomplete implementation (and probably should've used stack[n] everywhere instead of stack[n-1]). –  Izkata Oct 13 '13 at 15:41

Although Javascript doesn't have tail call optimization, recursion is often the best way to go. And sincerely, except in edge cases, you're not going to get call stack overflows.

Performance is something to keep in mind, but premature optimization too. If you think that recursion is more elegant than iteration, then go for it. If it turns out this is your bottleneck (which may never be), then you can replace with some ugly iteration. But most of the times, the bottleneck lies in the DOM manipulations or more generally the I/O, not the code itself.

Recursion is always more elegant1.

1: Personal opinion.

share
3  
I agree that recursion is more elegant, and elegance is important as it is readability as well as maintainability (this is subjective, but in my opinion recursion is very easy to read, thus maintainable). However, sometimes performance matters; can you support the claim that recursion is the best way to go, even performance-wise? –  mastazi Dec 18 '12 at 12:48
3  
@mastazi as said in my answer, I doubt that recursion is going to be your bottleneck. Most of the times, it's the DOM manipulation, or more generally the I/O. And don't forget that premature optimization is the root of all evils ;) –  Florian Margaine Dec 18 '12 at 12:49
    
+1 for DOM manipulation being a bottleneck most of the times! I remember a very interesting interview to Yehuda Katz (Ember.js) about this. –  mastazi Dec 18 '12 at 12:52
1  
@mike The definition of "premature" is "mature or ripe before the proper time." If you know that recursively doing something will cause a stackoverflow, then it's not premature. However, if you assume on a whim (without any actual data), then it's premature. –  Zirak Dec 18 '12 at 14:59
1  
With Javascript you don't how much stack the program will have available. You could have a tiny stack in IE6 or a big stack in FireFox. Recursive algorithms rarely have a fixed depth unless your doing a Scheme-style recursive loop. It just doesn't seem as if non-loop based recursion fits into avoiding premature optimizations. –  mike30 Dec 18 '12 at 21:20

As per request by the OP I'll chip in (without making a fool of myself, hopefully :P)

I think we're all agreed that recursion is just a more elegant way of coding. If done well it can make for more maintainable code, which is IMHO just as important (if not more) that shaving off 0.0001ms.

As far as the argument that JS does not perform Tail-call optimization is concerned: that's not entirely true anymore, using ECMA5's strict mode enables TCO. It was something I wasn't too happy about a while back, but at least I now know why arguments.callee throws errors in strict mode. I know the link above links to a bug report, but the bug is set to WONTFIX. Besides, standard TCO is coming: ECMA6 (December 2013).

Instinctively, and sticking to the functional nature of JS, I'd say that recursion is the more efficient coding style 99.99% of the time. However, Florian Margaine has a point when he says that the bottleneck is likely to be found elsewhere. If you're manipulating the DOM, you're probably best focussing on writing your code as maintainable as possible. The DOM API is what it is: slow.

I think it's nigh on impossible to offer a definitive answer as to which is the faster option. Lately, a lot of jspref's I've seen show that Chrome's V8 engine is ridiculously fast at some tasks, which run 4x slower on FF's SpiderMonkey and vice versa. Modern JS engines have all sorts of tricks up their sleeves to optimize your code. I'm no expert, but I do feel that V8, for example, is highly optimized for closures (and recursion), whereas MS's JScript engine is not. SpiderMonkey often performs better when the DOM is involved...

In short: I'd say which technique will be more performant is, as always in JS, nigh on impossible to predict.

share

I was pretty curious about this performance in javascript as well, so I did some experiments (albeit on an older version of node). I wrote a factorial calculator recursively vs iterations and ran it a few times locally. The result seemed pretty heavily skewed toward recursion having a tax (expected).

Code: https://github.com/j03m/trickyQuestions/blob/master/factorial.js

Result:
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:557
Time:126
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:519
Time:120
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:541
Time:123
j03m-MacBook-Air:trickyQuestions j03m$ node --version
v0.8.22
share

This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .