[프로그래머스][JS] 피보나치 수

문제

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 2 이상 100,000 이하인 자연수입니다.

솔루션1: 재귀(런타임에러)

const dp = {0: 0, 1: 1};

function solution(n) {
    if (n in dp) {
        return dp[n];
    }
    dp[n] = (solution(n-1) + solution(n-2)) % 1234567;
    return dp[n];
}

• 이전에 파이썬으로 풀던 것처럼 재귀를 사용해서 풀려고 시도했다.
• 테스트케이스 마지막 2개가 런타임 에러가 떴다.
• 자바스크립트에서 재귀 함수를 과도하게 많이 호출할 경우, "Maximum call stack size exceeded" 런타임 에러가 발생한다.

솔루션2: 반복문(성공)

const dp = [0, 1];

function solution(n) {
    if (n in dp) {
        return dp[n];
    }
    for (let i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
    }
    return dp[n];
}

• 그래서 그냥 반복문으로 바꿔서 해결했다.
• 자바스크립트에서 재귀를 사용하는 것을 주의해야겠다.