CODEWITHSUNDEEP
javascriptrecursiontail-recursion
Grant Everett
Grant Everett

Reputation: 103

Tail Recursion Optimization: Why does '+' not allow that?

So one of the common examples of tail recursion I see is:

function factorial(x) {
    if (x <= 0) {
        return 1;
    } else {
        return x * factorial(x-1); // (A)
    }
}

An it's optimized for Tail call with:

function factorial(n) {
    return facRec(n, 1);
}
function facRec(x, acc) {
    if (x <= 1) {
        return acc;
    } else {
        return facRec(x-1, x*acc); // (A)
    }
}

I get this. But my question is: Why isn't the * in this case a function that could be optimized on? Couldn't I rewrite the top as

function factorial(x) {
    if (x <= 0) {
        return 1;
    } else {
        return multiply(x, factorial(x-1)); // (A)
    }
}

I know this won't work. I think it's just because it's not a true tail recursive call? Would this still be tail optimized though?

Upvotes: 0

Views: 63

Answers (1)

T.J. Crowder
T.J. Crowder

Reputation: 1074148

Your last example isn't a tail call because you have to keep calling factorial before you can call multiply. Consider:

factorial(5)
  can't call multiply until it has the result from factorial(4)
    can't call multiply until it has the result from factorial(3)
      can't call multiply until it has the result from factorial(2)
        can't call multiply until it has the result from factorial(1)
          can't call multiply until it has the result from factorial(0)

it's only at this point that you stop recursing and call multiply. So, no tail call.

It's probably also worth noting that TCO is pretty much only implemented by Safari's JavaScriptCore. it isn't implemented by Chrome's V8 or Firefox's SpiderMonkey, nor is it likely to be, spec or no spec. :-) More here and here.

I should note that in your title you ask

Why does '+' not allow that?

It does. TCO doesn't care what the operation is — * vs + — just that it be in the tail position.

Upvotes: 7

Related Questions