Arithmetic progression using Recursion

Question

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

Answer 1

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

Answer 2

I am assuming this is a school assignment and an exercise in recursion. A short review;

• Its okay to have the recursive function be another function, but I imagine you get extra points for 1 single function
• Destructuring assignment helps with the signature function
• It's good that your first check in the recursive function is the exit condition
• Instead of swapping within the function, you can just call the function again with swapped arguments, super clear and 3 lines less of code

function sumRange([a,b]){

  if(a==b){
    return a;
  }else if(a>b){
    return sumRange([b,a]);
  }else{
    return b + sumRange([a,b-1]);  
  }
}

console.log(sumRange([1,3]));