[230411] 피보나치 수

 

 

문제

 

 

풀이

첫 풀이

function solution(n) {
    return fibo(n) % 1234567;
}

const fibo = (n) => {
    if(n === 0) return 0;
    if(n === 1) return 1;
    if(n === 2) return 1;
    return fibo(n-1) + fibo(n-2);
}

예상했겠지만, 이미 구한 피보나치 수를 또다시 구하는 구조이기 때문에 시간 초과가 발생해서 통과하지 못한다.

 

두 번째 풀이

이미 구한 피보나치 수는 배열(fiboArray)에 저장하는 구조로 재작성하였다.

const fiboArray = [0, 1, 1];

function solution(n) {
    return fibo(n);
}

const fibo = (n) => {
    if(fiboArray[n]) return fiboArray[n]
    fiboArray[n] = (fibo(n-1) + fibo(n-2)) % 1234567;
    return fiboArray[n];
}

그랬더니 테스트 13, 14에서 런타임 에러가 발생한다.

 

 

런타임 에러가 발생한 이유?

재귀호출은 호출이 가능한 깊이가 있다. 보통 자바스크립트 엔진에서 가능한 재귀호출의 깊이는 대부분 10000이다.

하지만 테스트 13, 14에서는 재귀 호출의 깊이를 초과했기 때문에 런타임 에러가 발생하는 것!

첫 번째 호출을 포함해서, 최대 중첩 호출의 수를 재귀 깊이라 한다. 최대 재귀 깊이는 자바스크립트 엔진에 따라 제한된다. 우리의 경우 10000이라 할 수 있지만, 몇몇 엔진들은 호출을 더 할수도 있다. 그치만 100000으로 대부분 제한된다. 이 제한을 완화하는데 도움주는 자동 최적화 가 있긴 하지만, 아직 많은 곳에서 지원하지 않고 있고, 단순한 경우에만 적용된다.

by. modern javascript

 

그래서 재귀함수가 아닌 다른 방법으로 문제를 풀어야 한다.

 

 

for문으로 풀기

function solution(n) {
    const fiboArray = [0, 1, 1];  
    if(n < 3) return fiboArray[n];
    
    for(let i = 3; i <= n; i++){
        fiboArray.push((fiboArray[i-1] + fiboArray[i-2]) % 1234567); 
    }
    return fiboArray[n];
}

통과!

 

 

 

 

 

---

참고 자료

[프로그래머스] 만만할 줄 알았던 피보나치 수 JS