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

// 테스트케이스 7번 부터 실패한 코드
function solution(n) {
    if(n===0) return 0;
    else if(n===1) return 1;
    else{
        return (solution(n-2)+solution(n-1))%1234567;
    }
}

재귀함수 연습하는 문제구나! 라고 생각해서 재귀를 사용해서 문제를 풀었는데..

7번부터 시간초과가 났고 13,14번은 런타임에러가 났다.

구글링을 좀 해보니 재귀로 풀면 안된다고만 얘기해주니

괜히 반발심이 생겨 재귀로 풀면 안되는 이유가 있는게 아니라면 납득하고 싶지 않았다.

 

재귀를 쓴다면 그 장점은 대표적으로 두가지다

1. 알고리즘을 재귀적으로 표현하는 것이 자연스러울 때

2. 변수 사용을 줄이기 위해

 

그렇다면 단점도 있을 것 같다.

1. 메모리를 많이 차지

2. 성능이 반복문에 비해 느리다

 

.... 시간초과가 나는 이유를 알았다!

반복문에 비해 느린 재귀를 사용해서 문제를 풀었으니 시간 초과가 났다.

 

하지만 한가지 더...

런타임 에러가 난 이유는 무엇일까?

 

결론부터

재귀호출은 호출이 가능한 깊이가 있고

13,14 테스트케이스에서는 그 깊이를 초과했기 때문이다!

 

보통 자바스크립트 엔진이 가능한 재귀호출의 깊이는 10000이고

가끔 100000을 허락하는 엔진이 있지만 대부분은 10000이라고 한다.

 

재귀에 대한 설명이 더 보고 싶다면 아래 링크를 확인해보면 좋을 것 같다.

javascript.info/recursion

Recursion and stack

아닌 사람은 코드!

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