1
\$\begingroup\$

take an array of two numbers who are not necessarily in order, and then add not just those numbers but any numbers in between. For example, [3,1] will be the same as 1+2+3 and not just 3+1.

function sumAll(arr) {
  let start = arr[0];
  let end = arr[1];
  if (start > end) {
    let temp = start;
    start = end;
    end = temp;
  }
  return getSum(start, end);
}
function getSum(start, end) {
  if (start === end) return start;
  return end + getSum(start, end-1);
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ There's absolutely no reason to use recursion for this. What is this code used for? Is this a school assignment? \$\endgroup\$ 20 hours ago
  • \$\begingroup\$ For [n,m] the sum of all integers among n and m would be (m-n+1) . (n+m) / 2 where m > n. \$\endgroup\$
    – Redu
    19 hours ago
2
\$\begingroup\$

Recursion

Recursion in JavaScript is just a toy and should be avoided when ever possible.

Why?

  • Untrustable. JavaScript has a very limited call stack and recursive code can quickly consume the call stack. For example getSum(1, 10000) will overflow the call stack and throw an error.

    Example showing call-stack overflow.

   
sumAll([0, 10000]);
function getSum(start, end) {
  if (start === end) return start;
  return end + getSum(start, end-1);
}
function sumAll(arr) {
  let start = arr[0];
  let end = arr[1];
  if (start > end) {
    let temp = start;
    start = end;
    end = temp;
  }
  return getSum(start, end);
}

  • Very Slow. JavaScript does not have proper tail calls, meaning each call requires a call stack operation that captures the call's new context. This is a very slow operation when compared to (in this case) adding two values.

    There is also the overhead of returning which requires yet another call stack (pop) operation

  • Memory hungry. It is very memory inefficient, as it has a minimum storage cost of \$O(n)\$ which in this case is very bad as the task in this case has a storage cost of \$O(1)\$

  • Because of the chance of a thrown error (That can not be predicted) you should always wrap recursive calls inside a try catch. Unfortunately JavaScript, inside and around the try catch (not just inside the try) can not be optimized. It is automatically marked (Do Not Optimize)

    As you are forced to use the try catch to avoid having your code crash the recursion is further degraded by the lack of active optimization.

Example

The code below measures the performance of recursion with try catch, recursion without try catch and a simple while loop.

The results speak for them selves.

Recursion in JavaScript should be avoid when ever possible!!!

function getSum(start, end) {
  if (start === end) return start;
  return end + getSum(start, end-1);
}
function sumAll(arr) {
  let start = arr[0];
  let end = arr[1];
  if (start > end) {
    let temp = start;
    start = end;
    end = temp;
  }
  return getSum(start, end);
}
function sumAll_Catches(arr) {
  let start = arr[0];
  let end = arr[1];
  if (start > end) {
    let temp = start;
    start = end;
    end = temp;
  }
  try { return getSum(start, end); }
  catch(e) { console.log(e.message); }
}

/* Uses while loop to get sum */
function sumAll_B([a, b]) { return a > b ? getSum_B(b, a) : getSum_B(a, b) }
function getSum_B(start, end) {
  var sum = start++;
  while (start <= end) { sum += start++ }
  return sum;
}
/* for calibrating number of cycles needed to get good test data */
function Calibrator([start, end]) {
  var sum = start++;
  while (start <= end) { sum += start++ }
  return sum;
}

var testCount = 500;
const testData = [0, 3000];
function Test(name, call, ...data) {
   var i = testCount - 1;
   const now = performance.now();
   while (i--) { call(...data) }
   const res = call(...data);
   const time = performance.now() - now;
   name != "" && console.log("Test: " + name + " Result: " + res + " Time: " + (time / testCount).toFixed(3) + "ms per call.");
   return time;
}

while (Test("", Calibrator, testData) < 2.5) { testCount += 150; }
console.log("Cycles per test: " + testCount);
console.log("Test data: [" + testData + "]");
Test("Recursion catch. ", sumAll_Catches, testData);
Test("Recursion ...... ", sumAll, testData);
Test("While loop...... ", sumAll_B, testData);

Summing consecutive numbers

There is no need to manually sum a list of numbers as the task has a time complexity of \$O(1)\$ and using a loop is at best \$O(n)\$

Rewrite

Time and storage \$O(1)\$

Note that the code is only for positive numbers, but can easily be adapted to include negative values.

function sumAll([a, b]) {
   a = Math.abs(a);  /* Only for positive values */
   b = Math.abs(b);
   b < a && ([a, b] = [b, a]);
   a -= 1;            /* To match your original code */
   return b * (b + 1) / 2 - a * (a + 1) / 2;
}
console.log(sumAll([2, 3000]));

\$\endgroup\$
2
  • \$\begingroup\$ I mostly agree that recursion should be avoided in JS however sometimes it yields to brilliant code in a few lines. \$\endgroup\$
    – Redu
    13 hours ago
  • \$\begingroup\$ Kindly at your earliest convenience if you may, what do you think time complexity is here. \$\endgroup\$
    – Redu
    7 hours ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.