Using exceptions to simulate tail recursion in JavaScript

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-fuGimp extension based on scheme).

, ,

  1. #1 by Łukasz Wójciak (@lukaszwojciak) on March 19, 2014 - 10:13

    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);
    }

    ?

    • #2 by jcubic on March 19, 2014 - 10:25

      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.

  2. #3 by tungsten94 on March 19, 2014 - 12:18

    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).

    • #4 by jcubic on March 20, 2014 - 11:02

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

      • #5 by tungsten94 on March 20, 2014 - 20:29

        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.

      • #6 by jcubic on March 20, 2014 - 21:41

        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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: