18

I know you should tread lightly when making recursive calls to functions in JavaScript because your second call could be up to 10 times slower.

Eloquent JavaScript states:

There is one important problem: In most JavaScript implementations, this second version is about 10 times slow than the first one. In JavaScript, running a simple loop is a lot cheaper than calling a function multiple times.

John Resig even says this is a problem in this post.

My question is: Why is it so inefficient to use recursion? Is it just the way a particular engine is built? Will we ever see a time in JavaScript where this isn't the case?

Mike Fielden
  • 10,055
  • 14
  • 59
  • 99
  • 1
    I'm guessing it's a scope thing :P Great question, I'm curious what they answer is! – Pelshoff Aug 17 '11 at 17:29
  • 4
    Function call overhead is simply greater than that of loop control; that's true in just about any programming language. There's a lot more bookkeeping to do when calling a function: allocate and initialize a new scope, save the return address, marshal the parameters, etc. Note that JavaScript interpreters have been getting faster at a very fast pace, so performance tips in a 3 year old blog post (or book) should be questioned. – Pointy Aug 17 '11 at 17:38
  • 1
    "because your second call could be up to 10 times slower" That's not what the text says. It says that the second version of the code is 10 times slower. – Rag Aug 17 '11 at 18:16
  • [This](http://jsperf.com/recursive-process) is a good demonstration of how slow recursion can be. Notice it isn't just the function calls that make the difference as both tests have the same number of calls – Jake Jul 03 '12 at 08:44

2 Answers2

11

Function calls are just more expensive than a simple loop due to all the overhead of changing the stack and setting up a new context and so on. In order for recursion to be very efficient, a language has to support some form of tail-call elimination, which basically means transforming certain kinds of recursive functions into loops. Functional languages like OCaml, Haskell and Scheme do this, but no JavaScript implementation I'm aware of does so (it would only be marginally useful unless they all did, so maybe we have a dining philosophers problem).

Chuck
  • 234,037
  • 30
  • 302
  • 389
  • 5
    ES6 should have tail call optimisation. [Proper tail calls](http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls) – Raynos Aug 17 '11 at 18:12
3

This is just a way the particular JS engines the browsers use are built, yes. Without tail call elimination, you have to create a new stack frame every time you recurse, whereas with a loop it's just setting the program counter back to the start of it. Scheme, for example, has this as part of the language specification, so you can use recursion in this manner without worrying about performance.

https://bugzilla.mozilla.org/show_bug.cgi?id=445363 indicates progress being made in Firefox (and Brendan Eich speaks in here about it possibly being made a part of the ECMAScript spec), but I don't think any of the current browsers have this implemented quite yet.

rwat
  • 833
  • 5
  • 10