📚 문제

피보나치 수
https://programmers.co.kr/learn/courses/30/lessons/12945

💡 접근

• 처음 풀었던 방법

function solution(n){
  if (n == 0) return 0;
  else if (n == 1) return 1;
  else return (solution(n-1) + solution(n-2)) % 1234567

재귀함수로 푸는 줄 알고 아 쉽넹 하고 풀었는데 테케 7번부터 시간초과, 11번부터 런타임에러 가 나면서 틀렸다. 질문하기 들어가서 확인해보니 모듈러 연산이 문제인줄 알고

• 모듈러 연산 성질
  (A+B) % C = ((A%C) + (B%C)) % C

마지막 줄을 요로케 고쳤는데 그래도 결과는 같았다.

알고보니 재귀가 문제였다.

1. 시간초과 - 재귀의 단점 때문
   • 재귀 사용의 단점
     • 메모리를 많이 차지한다.
     • 성능이 반복문에 비해 느리다.
   • 재귀 사용의 장점
     • 알고리즘을 재귀적으로 표현하는 것이 자연스러울때
     • 변수 사용을 줄일 수 있다.
2. 런타임 에러 - 재귀 깊이를 넘어간 것 같다.
   • 가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수는 재귀 깊이(recursion depth) 라고 한다.
   • 자바스크립트 엔진은 10000개 까지는 확실히 허용한다. 대다수 엔진이 십만까지는 다루지 못한다.

따라서 재귀를 버리고 반복문으로 풀었다.

⌨️ 코드

function solution(n){
    const fibo = [0,1];
    
    for (let i = 2; i <=n; i++){
        fibo[i] = ((fibo[i-1]%1234567) + (fibo[i-2]%1234567)) % 1234567;
    }

    return fibo[n];
}

📝 리뷰

재귀 깊이, 모듈러 연산 성질 등 컴퓨터과학에 관련한 지식? 을 알 수 있었둥