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.