3

While solving fabonocci problem using recursion and memoization in JavaScript, I got "Maximum Call Stack Exceeded" error when I try to run it with large inputs. To troubleshoot, I copied the solution from GeeksforGeeks (GFG) and that works correctly. However, I'm struggling to understand why my approach fails.

Here is my code

function topDown(n) {
  const modulus = 10 ** 9 + 7;
  const dp = {};
  function rec(value) {
    if (value <= 1) {
      return value;
    }
    if (dp[value] !== undefined) {
      return dp[value];
    }
    dp[value] = (rec(value - 1) + rec(value - 2)) % modulus;
    return dp[value];
  }
  return rec(n);
}

Here is working solution

function topDownTwo(n) {
  const modulus = 10 ** 9 + 7;
  const dp = {};
  function rec(value) {
    if (value <= 1) {
      return value;
    }
    if (dp[value] !== undefined) {
      return dp[value];
    }
    const ans = (rec(value - 1) + rec(value - 2)) % modulus;
    dp[value] = ans;
    return ans;
  }
  return rec(n);
}

Only difference is how value is returned from recursive function.

dp[value] = (rec(value - 1) + rec(value - 2)) % modulus;
return dp[value];

and

const ans = (rec(value - 1) + rec(value - 2)) % modulus;
dp[value] = ans;
return ans;

When I call these functions with a large value of n, like 9657, my version throws a stack overflow error, while the GFG version runs without any issues.

I'd appreciate any help in understanding the cause of this issue.

10
  • Well, you are creating a variable on the stack, which the original code does not. Stack frames use memory, and you will have one for each level in the recursion. Commented Aug 9, 2024 at 4:49
  • 1
    @TimRoberts wouldn't that mean though that the 2nd code snippet would be the one we'd expect to fail, not the first 🤔 Commented Aug 9, 2024 at 4:57
  • 1
    FYI, in my browser, both are failing. Commented Aug 9, 2024 at 4:58
  • I tried and found that both functions throw maximum call stack error, are you sure that the 2nd function worked? Commented Aug 9, 2024 at 5:08
  • I can repro in Chrome, using 7000 as input. In Firefox, passing 15000, it's complete random, sometimes both fail, or both pass or any pass... I'd suspect JIT inlining might be a reason why one can go a bit farther than the other, but that's just speculation. User jrmk will know better. Commented Aug 9, 2024 at 5:12

0

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.