3

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

Improve this question
3
  • 3
    Note: factorial will also throw a stack overflow if you raise the number from 10,000. It's not immune to a stack overflow, it just happens to be below the limit right now. I'm not sure why sumAll is reaching the limit, despite apparently recursing the same number of times. Commented Jan 3, 2022 at 14:49
  • 3
    It almost certainly has to do with the memory on the stack, as this version does not overflow: function sumAll(n) {return (n == 0) ? 0 : n + sumAll(n - 1);} -- a restructuring of the sumAll function to look like the factorial one. I know there are some v8 folks around here who are good at answering these, but I can't recall any handles ATM. Commented Jan 3, 2022 at 21:57
  • Hope this answer helps in providing some reasoning. stackoverflow.com/a/70582249/6160525 Commented Jan 4, 2022 at 16:51

2 Answers 2

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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.

Improve this answer

7 Comments

This would make sense as an explanation if the second function resulted in a stack overflow but the first doesn't - but in fact if you read the OP (and try the snippets), you'll see it's the other way round. (I believe the reason the second doesn't overflow is that the result reaches Infinity before the call-stack size is exceeded. I'm not sure why the first is erroring with a stack overflow since, as you point out, it should be making use of TCO.)
@RobinZigmond you're absolutely right, whoops.
@RobinZigmond even if you modify factorial to return the incorrect value of factorial((n-1)), still factorial does not raise the StackOverflow error and it did not reach Infinity either
@MasterOfTheHouse I'm just going off the behaviour in the snippet here on Stack Overflow - for me, in Chrome, it more or less instantly gives an answer of Infinity. I do realise though that this is running in a browser rather than NodeJS
@RobinZigmond Yes I see the same in Chrome.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.