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]));
[n,m]
the sum of all integers amongn
andm
would be(m-n+1) . (n+m) / 2
wherem > n
. \$\endgroup\$