I am trying to solve a problem of leetcode through recursion but I am getting an error saying RangeError: Maximum call stack size exceeded
maybe I am doing something wrong.
Problem:
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy.
Return true if n
is a happy number, and false
if not.
Example 1:
Input: n = 19
Output: true
Explanation:
12 92 = 82
82 22 = 68
62 82 = 100
12 02 02 = 1
Example 2:
Input: n = 2
Output: false
My Code:
var isHappy = function(n) {
if(n.length<2) return false
var fn=(n)=>{
let i=0;
let sum=0;
while(i<n.length){
sum=sum Math.pow(n[n.length-1-i],2);
i ;
}
while(sum!==1){
//console.log(sum)
fn(sum);
}
if(sum === 1) return true
}
fn(n)
};
PS: I don't need a solution for this problem. I want to find out why my code isn't working and What I am doing wrong. And, What changes should I make so that it works fine.
Link to the above problem.
CodePudding user response:
As you wrote yourself, "Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle".
In your implementation, fn
calls itself infinitely. In the process, the javascript virtual machine creates a fonction context in memory at each iteration. This can be done up to a certain times after which the error Maximum call stack size exceeded
throws.
What I am doing wrong?
You return true when you find a happy number, but you never return false otherwise. Add a condition to detect unhappy numbers (detect a cycle) and return false in that case.
Edit: here is an example implementation:
var isHappy = function(n) {
if(n.length<2) return false
// placeholder to store already called values
const calledValues= new Set()
var fn=(n)=>{
let i=0;
let sum=0;
if (calledValues.has(n))
// cycle detected!
return false;
calledValues.add(n);
while(i<n.length){
sum=sum Math.pow(n[n.length-1-i],2);
i ;
}
if (sum !== 1)
return fn(sum.toString());
else
// sum === 1, number is happy!
return true
}
// make sure to pass a string to fn
return fn(n.toString());
};
(new Array(20)).fill().map((_,i)=>10 i)
.forEach(n=> console.log(n, "is happy?", isHappy(n)));
CodePudding user response:
Maximum call stack size exceeded
This error occurs when functions call other functions too many times. In this case, your function calls itself recursively with no end, should the number be an "unhappy" one.
Consider adding into your function something which allows you to tell if the process loops endlessly.
Consider using arguments/arrays to store what numbers have already turned up.