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

Question

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?

@Grant Everett: please change your title, and I'd be happy to "upvote" your question. Please "upvote" and "accept" T.J. Crowder's Most Excellent response, if it answers your question. — FoggyDay, Jan 14 '20 at 22:57
I'm new to asking questions here. Do I just change it to "Solved"? — Grant Everett, Jan 17 '20 at 18:19

T.J. Crowder · Accepted Answer · 2020-01-14T22:47:23.567

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.

Thanks so much! This is really helpful :) – Grant Everett Jan 17 '20 at 18:20 — Grant Everett, Jan 17 '20 at 18:20

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

1 Answers1