[Javascript 오류] RangeError: Maximum call stack size exceeded

백준에서 dfs(재귀함수)를 이용해 2023번 문제를 풀던 중 실행을 했을 때 다음의 오류를 마주했다.

 

 

원본 코드

//2023번: 신기한 소수

const fs = require('fs');
const N = Number(fs.readFileSync('예제.txt', 'utf8').trim()); // 백준 경로:'/dev/stdin'

const dfs = (currentNum, currentDigit) => {
    if(currentDigit === N){
        if(isPrimeNumber(currentNum)){
            console.log(currentNum);
            return;
        }
    }
    for(let i=1;i<10;i++){ //뒤에 붙는 수
    	const nextNum = currentNum * 10 + i; //뒤에 붙는 수
        if(isPrimeNumber(nextNum)){
            dfs(nextNum,currentDigit+1);
        }
    }
};

//소수 구하기 함수
const isPrimeNumber = (number) =>{
    for(let i=2;i<=number/2;i++){
        if(number % i ===0) return false;
    }
    return true;
}


dfs(2,1);
dfs(3,1);
dfs(5,1);
dfs(7,1);

 

원인

이는 재귀함수의 호출이 너무 깊어졌기 때문에 발생하는 오류이다.

 

내 코드의 문제점을 살펴보면 dfs 함수에서 조건에 해당되지 않을 경우 종료하는 로직을 넣지 않았기 때문에 무한재귀에 빠지게 된다. return; 문의 위치를 if 조건 바깥에 두어야한다.

또 코드를 최적화하기 위해 살펴보면, 1을 재귀호출에서 제외하지 않았다.

소수를 판별하는 함수(isPrimeNumber)의 경우에도 number/2 대신 Math.sqrt(number)까지만 검사해도 충분히 소수 판별이 가능하다.

해결

이 문제는 백준에서 node.js를 쓰면 재귀때문에 메모리 초과가 난다. 로직 공부용으로만 보기

const fs = require('fs');
const N = Number(fs.readFileSync('예제.txt', 'utf8').trim()); // 백준 경로:'/dev/stdin'

const dfs = (currentNum, currentDigit) => {
    if(currentDigit === N){
        if(isPrimeNumber(currentNum)){
            console.log(currentNum);
        }
        return;
    }
    
    for(let i=1;i<10;i++){ 
        const nextNum = currentNum * 10 + i; //뒤에 붙는 수
        if(isPrimeNumber(nextNum)){
            dfs(nextNum,currentDigit+1);
        }
    }
};

//소수 구하기 함수
const isPrimeNumber = (number) =>{
    if(number<2) return false;
    for(let i=2;i<=Math.sqrt(number);i++){
        if(number % i ===0) return false;
    }
    return true;
}


dfs(2,1);
dfs(3,1);
dfs(5,1);
dfs(7,1);