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

피보나치 수 문제를 푸는데 13번, 14번 테스트 케이스에서 계속 런타임 에러가 발생했다.

아래는 나의 JavaScript code이다.

function solution(n) {
    // 피보나치 수열의 첫번째(index:0), 두번째(index:1)의 값은 1이다.
    let f = [1, 1]
    let fib = (n) =>{
        // 이미 저장된 값이 있다면 해당 값 재사용. 이 과정이 없으면 불필요한 재귀 발생
        if(f[n] != undefined){
            return f[n]
        }else{  // 저장된 값이 없다면 값 도출하여 저장
            f[n] = fib(n-1) + fib(n-2)
            return f[n] % 1234567
        }
    }
    return fib(n-1)
}

왜 런타임 에러가 날까 서치해봤는데,

JavaScript의 재귀 호출 깊이가 타 언어에 비해 작기 때문에 발생하는 런타임 에러였다!
이 문제를 해결하려면
1. 재귀 호출이 아닌 반복문(for문)으로 풀기
2. 다른 언어로 풀기(;;)
가 있다.

다른 언어로 풀 수도 있겠지만 이런 문제 때문에 언어를 바꾼다는건... 자존심이 상하기때문에 for문으로 다시 풀어보았다.

function solution(n) {
    // 피보나치 수열의 첫번째(index:0), 두번째(index:1)의 값은 1이다.
    let f = [1, 1]
    for(let i = 2 ; i < n ; i++){
    	// for문으로 돌기때문에 f[index-1]값이 있는지 확인할 필요가 없다.
        f[i] = (f[i-1] + f[i-2]) % 1234567
    }
    return f[f.length-1]
}

성공!!

이번 기회에 JavaScript의 스택사이즈를 알아볼 수 있어 좋았다. 또 피보나치 수를 다시 학습할 수 있어 즐거웠다.!!