Two recursive functions and stackoverflow errors in javascript/nodeJs. Understanding the differences

user_8661071 0
Viewed 83

Looking into the SICP book and JS functional programming I created two recursive functions. My expectation was that both of them raised a stack overflow error. But it is only the sumAll() function that raised the error. See below the code for both functions sumAll() and factorial():

As expected the sumAll() function did raise a stack overflow error

function sumAll(n, i = 0, result = 0) {
  return (i > n)
    ? result
    : sumAll(n, i + 1, i + result);
}
    
console.log(sumAll(10000));

The factorial() function below did not raise a stack overflow error:

function factorial(n){
  return (n == 1)
    ? 1
    :  n* factorial((n-1))
}
    
console.log(factorial(10000))

My question is why the factorial() function does not raise a stack overflow and works perfectly in nodeJS meanwhile the sumAll() did raise it also in nodeJS

node.js stack-overflow tail-recursion recursion javascript
2 Answers

The number of local variables (i.e memory of local variables) is also considered in the call stack size.

function computeMaxCallStackFrames(a, b, c, d) {
  try {
    return 1 + computeMaxCallStackFrames(a + 1, b + 1, c + 2, d + 3);
  } catch (e) {
    // Call stack overflow
    // console.log(e);
    return 1;
  }
}
var stackFrames = computeMaxCallStackFrames(1, 4, 6, 2);
console.log(stackFrames);

try increasing the no. of parameters, you'll see the decrease in number of recursion calls / call stack frames.

function computeMaxCallStackFrames(a, b, c, d, e) {
  try {
    return 1 + computeMaxCallStackFrames(a + 1, b + 1, c + 2, d + 3, e-2);
  } catch (e) {
    // Call stack overflow
    // console.log(e);
    return 1;
  }
}
var stackFrames = computeMaxCallStackFrames(1, 4, 6, 2, 9);
console.log(stackFrames);

with zero local variables.

function computeMaxCallStackFrames() {
  try {
    return 1 + computeMaxCallStackFrames();
  } catch (e) {
    // Call stack overflow
    // console.log(e);
    return 1;
  }
}
var stackFrames = computeMaxCallStackFrames();
console.log(stackFrames);

So, we can clearly see that the number of local variables (i.e memory of local variables) is also considered in the call stack size. If there are many local variables then the no. of recursive calls will be less.

Edit: And we all know the stack size will vary from browser to browser. So the output will not be same in different browsers, but it should be consistent in the same browser even if we run it multiple times.

Hope it all makes sense now.

user_61605250

I gave the below answer in error, I got mixed up about which function was throwing the exception. Please ignore.

Your first function is capable of taking advantage of tail-call optimization, while your second function is not (or it is, but perhaps not in a way that's implemented in the node.js language).

Consider this: your first function's usual condition is that it ends in return sumAll(n, i + 1, i + result), which means that once you get something to return, you can just return that.

Your second function however ends in return n* factorial((n-1)), which means that once you get something to return, you have to do ANOTHER operation on it (multiply it by n) before you can actually return the result.

I believe the node.js interpreter isn't able to tail-call-optimize the second function because it requires another operation to be performed on it before the return.

Please note: I am not certain this is the answer, and I suspect node.js may not support tail call optimizations of any sort. This is my theory though about why one function might error in that way and the other one wouldn't.

user_19590540
Related