4

So I wrote this function that sums an array of numbers using recursion. How would I make this tail call optimized?

function sum(array) {
  if (array.length === 0) {
    return 0;
  } else {
    return array[0] + sum(array.slice(1));
  }
}

sum([1, 2, 3, 4, 5]); // 15
Animal Rights
  • 9,107
  • 6
  • 28
  • 40
  • What do you mean, *optimized*? Smaller? Shorter? – Jack Bashford Apr 02 '19 at 07:25
  • I wouldn't say 'duplicate', but the question [What Is Tail Call Optimization?](https://stackoverflow.com/questions/310974/what-is-tail-call-optimization) shows a nice example on how to make the Factorial function tail call optimized. – GolezTrol Apr 02 '19 at 07:26
  • @JackBashford I may be wrong but I think the question simply refers to tail call optimization as explained here: https://stackoverflow.com/questions/310974/what-is-tail-call-optimization not optimized in terms of the actual code which is written – OliverRadini Apr 02 '19 at 07:27
  • It may also be worth noting that support for tail call optimization is fairly poor https://kangax.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation) – OliverRadini Apr 02 '19 at 07:43

4 Answers4

3

A TCO function needs to return a function call, which replaces the last stack item and prevents the stack to grow.

Therfore you need to store the total as well in the function as parameter and hand over this value at the ent of the recursion.

function sum(array, total = 0) {
    if (array.length === 0) {
        return total;
    } 
    return sum(array.slice(1), total + array[0]);
}

console.log(sum([1, 2, 3, 4, 5])); // 15
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
0

Using Array.prototype.reduce() there is no need to do a recursive function:

const result = [1, 2, 3, 4, 5].reduce((a, c) => a + c, 0); // 15

console.log(result);
Yosvel Quintero
  • 18,669
  • 5
  • 37
  • 46
0

Just use a ternary operator like so:

const sum = array => array.length ? array[0] + sum(array.slice(1)) : 0;

console.log(sum([1, 2, 3, 4, 5])); // 15

You can also use Array.prototype.reduce to avoid recursion:

const sum = array => array.reduce((acc, curr) => acc + curr, 0);

console.log(sum([1, 2, 3, 4, 5]));
Jack Bashford
  • 43,180
  • 11
  • 50
  • 79
0

You can't, tail call optimization (TCO) is not supported in most of browser. You can see support info here.

You can always use for loop. for loop has higher performance in most of situation.

function getRandomInt(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min)) + min; //不含最大值，含最小值
}

function sum_1(arr) {
  var s = 0;
  for (var i = 0; i < arr.length; i++) {
    s += arr[i];
  }
  return s;
}

function sum_2(arr){
  return arr.reduce((a, c) => a + c, 0);
}

var arr = [];
for (var i = 0; i < 10000000; i++) {
  arr[i] = getRandomInt(0,100);
}

let t0 = window.performance.now();
sum_1(arr); // 15
let t1 = window.performance.now();
console.log("sum_1 executed time : " + (t1 - t0) + " ms");


let t2 = window.performance.now();
sum_2(arr); // 15
let t3 = window.performance.now();
console.log("sum_2 executed time : " + (t3 - t2) + " ms");
yip102011
  • 751
  • 4
  • 11