CODEWITHSUNDEEP
javascriptrecursionecmascript-6tail-call-optimization
Ben Aston
Ben Aston

Reputation: 55729

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

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?

Upvotes: 3

Views: 451

Answers (1)

Bergi
Bergi

Reputation: 664548

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

Upvotes: 6

Related Questions