31

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.

Martijn Pieters
  • 14,499
  • 10
  • 57
  • 58
mastazi
  • 413
  • 1
  • 5
  • 8
  • 3
    Make your own test and find out right away at http://jsperf.com/ – TehShrike Dec 18 '12 at 16:44
  • with the bounty and one answer mentioning TCO. It appears that ES6 specifies TCO but so far nobody implements it if we believe https://kangax.github.io/compat-table/es6/ Am I missing something? – Matthias Kauer Oct 08 '15 at 00:56

5 Answers5

37

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.

Community
  • 1
Triang3l
  • 815
  • 9
  • 12
  • 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 09: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](http://en.wikipedia.org/wiki/Flood_fill#Alternative_implementations). – Triang3l Jan 06 '13 at 17:37
  • It's worth noting that a language doesn't perform TCO, but an implementation might. The way that people optimize JS means that perhaps TCO could appear in a few implementations – daniel gratzer Oct 13 '13 at 13:41
  • 1
    @mastazi Replace the `else` in that function with `else if (stack[n-1]) { return stack[n-1]; } else` and you have [memoization](http://en.wikipedia.org/wiki/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
  • Thank you @Izkata, I often do that kind of optimisation but until today I didn't know its name. I should have studied CS instead of IT ;-) – mastazi Oct 14 '13 at 02:16
22

Update: since ES2015, JavaScript has TCO, so part of the argument below doesn't stand anymore.

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.

Florian Margaine
  • 6,791
  • 3
  • 33
  • 46
  • 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
  • 4
    @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
  • @mastazi yeah, the DOM is effin' slow. – Florian Margaine Dec 18 '12 at 12:54
  • Try implementing fill algorithm with recursion. Stack overflow! There's so many cases where the stack gets too deep I wouldn't call it an edge case or even premature. Space is a part of performance too, not just response time and throughput. – mike30 Dec 18 '12 at 14:20
  • Well, sorry, I don't implement fill algorithms every day. I take space into performance too. This is also taken into premature optimization in today's world. – Florian Margaine Dec 18 '12 at 14:53
  • 1
    @mike The [definition of "premature"](http://dictionary.reference.com/browse/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
  • 2
    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
  • Tiny stack? Really? Over 1000 is tiny? You've got something else wrong if you need so many recursions. – Florian Margaine Dec 18 '12 at 21:36
  • 1000 bytes? Yes that is extremely small. Even smaller that I thought. Process an image recursively and it will not work even on small images. Even little data structures will quickly fill up the stack several levels deep. – mike30 Dec 18 '12 at 21:41
  • That's not bytes, that's the number of times a function can recurse. – Florian Margaine Dec 19 '12 at 08:09
  • @FlorianMargaine. Maybe some browsers put a cap on stack depth. But even if a cap is set at one trillion, the issue remains if the stack size itself is tiny. Try it yourself. Make a javascript program to read human verification images when you create an account on a website. Run it on IE6. Recursion is the most natural technique for finding the letters and fits like a glove. But you won't be able to use it. – mike30 Dec 19 '12 at 14:23
7

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
Dr.HappyPants
  • 193
  • 1
  • 4
  • You could try this with `"use strict";` and see if it makes a difference. (It will produce `jump`s instead of the standard call sequence) – Burdock Oct 07 '15 at 06:00
  • 1
    On a recent version of node (6.9.1) I got extremely similar results. There's a bit of a tax on recursion, but I consider it an edge case - 400ms difference for 1,000,000 loops is .0025 ms per loop. If you are doing 1,000,000 loops it is something to keep in mind. – Kelz Apr 19 '17 at 00:19
  • i really don't think you should use a `random` in the code, if you set the number to `100` for all three cases, i would be more convincing. But either way, in my computer the time saved between iteration and recursive is 13/1. That's a bit crazy. – windmaomao Jan 06 '22 at 01:39
6

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.

Community
  • 1
Elias Van Ootegem
  • 473
  • 2
  • 14
3

Without strict mode, Iteration performance is usually slightly faster then recursion (in addition to making the JIT do more work). Tail recursion optimization essentially eliminates any noticeable difference because it turns the whole call sequence to a jump.

Example: Jsperf

I would suggest worrying much more about code clarity and simplicity when it comes to choosing between recursion and iteration.

Burdock
  • 203
  • 1
  • 4