JavaScript is very powerful language but it don’t have tail call elimination. But it turn out that you can simulate it using exception system. Here is very simple recursive function that calculate factorial:

function factorial(n) {
function recur(n, result) {
if (n == 0) {
throw result;
} else {
recur(n-1, result*n);
}
}
try {
recur(n, 1);
} catch(e) {
return e;
}
}

It turn out that in JavaScript (I read that in Douglas Crockford book **JavaScript: The Good Parts**) you can use any expression in throw and it will be send to variable in catch statement.

So what the above code does it simple exit from the recursive loop and pass result to catch statement. And this is exactly what tail recursion is, in language scheme this happen by default when inner function (you also need to create inner function in scheme) have recursive call as last expression. Here is scheme version of tail recursive factorial:

(define (factorial n)
(let recur ((n n) (result 1))
(if (= n 0)
result
(recur (- n 1) (* result n)))))

the code use named let but it can be rewriten with inner function and invocation. (this kind of trick is needed in **script-fu** – Gimp extension based on scheme).

### Like this:

Like Loading...

How is this different from:

function factorial(n) {

function recur(n, result) {

if (n == 0) {

return result;

} else {

return recur(n-1, result*n);

}

}

return recur(n,n);

}

?

I’ve just realized that the stack is still created in contrast with scheme. I think that trampoline is the best way to create stackless recursive loops, setTimeout just don’t look as good.

I think that your factorial function is broken. factorial(2) gives 4. I think that the error is at recur(n, n). It should be recur(n, 1).

Yea, you’re right, Updated. Thanks for pointing that out.

Great article. But the error still persists in scheme: (factorial 2) returns 4. Same solution. (let recur ((n n)…

should be (let recur ((n 1)…

I ran some benchmarks. And the exception version in javascript runs a bit faster (in node). I will look in to exactly how much faster.

Updated scheme, but actually it should be `(let recur ((n n) (result 1))`.

JSPerf show that they about the same: http://jsperf.com/exception-exit-test

And node use the same js engine as chromium(chrome). Maybe other engines act differently.