How to modify this code to enable tail call optimization in ES6?

Question

I have written a function to sum values recursively, but it does not meet the criteria for tail call optimization in ES6 (for reasons I cannot articulate).

function sum(...values) {
  if(!values.length) { 
    return 0; 
  }
  return values.shift() + sum(...values);
}

How can I change it to be eligible for optimization?

possible duplicate of [What Is Tail Call Optimization?](http://stackoverflow.com/questions/310974/what-is-tail-call-optimization) — Andreas, Apr 15 '15 at 14:15
The general way to do that is to pass along an accumulator parameter of some sort. Personally I would just declare a local function that takes an extra parameter; I'd give an example but I'm not good at ES6 syntax yet :) — Pointy, Apr 15 '15 at 14:17
Ha ha I had typed in a function almost exactly like Bergi's answer but decided it was probably wrong. — Pointy, Apr 15 '15 at 14:18
I don't think this should be closed. It is topically similar to the linked question, but this is about JavaScript and is a fine example. — Pointy, Apr 15 '15 at 14:23

Bergi · Accepted Answer · 2015-04-15T14:31:07.247

6

You need to do

return sum(…);

to make a proper tail call. In your example, the + operation is still executed after the recursive call, which makes this not work.

The typical approach is to use a helper function with an accumulator parameter:

 function sum(...values) {
     function sumTo(acc, values) {
         if (!values.length) return acc;
         else return sumTo(acc+values.shift(), values); // tail-recursive call
     }
     return sumTo(0, values);
 }

When recursing over lists, you can also (ab)use the list itself:

function sum(...values) {
    switch (values.length) {
        case 0:  return 0;
        case 1:  return values[0];
        default: values.unshift(values.shift()+values.shift());
                 return sum(...values);
    }
}
// or alternatively:
function sum(acc, ...values) {
    switch (arguments.length) {
        case 0:  return 0;
        case 1:  return acc;
        default: values[0] += acc;
                 return sum(...values);
    }
}

edited Apr 15 '15 at 14:31

answered Apr 15 '15 at 14:15

Bergi

630,263
148
957
1,375

Right - but is that really how you invoke a `. . .` function with an array parameter? I haven't worked with that ES6 stuff yet. – Pointy Apr 15 '15 at 14:18
@Pointy: `sum !== sumTo`. `sum` is never called in this example. – Felix Kling Apr 15 '15 at 14:19
@FelixKling yes, but ... oh I see. Ah, duhh, that makes sense. It's an array already. – Pointy Apr 15 '15 at 14:19
@Pointy: Should I use `...` for `sumTo` as well to make it clearer? I was not sure. – Bergi Apr 15 '15 at 14:25
@Bergi no I think it's fine; I was just confused. I think (if you used `...`) you'd need to invoke it with `.apply()` and it'd be kind-of a mess, no? – Pointy Apr 15 '15 at 14:26
@Pointy: I thought that as well, but actually `sumTo(acc, ...values)` would work. Regardless, I think it is much cleaner to use single arguments for lists if you have multiple parameters. After all, this question is about tail calls, not about spread parameters :-) – Bergi Apr 15 '15 at 14:30

How to modify this code to enable tail call optimization in ES6?

1 Answers1