재귀함수를 이용하여 n번째 피보나치 수를 구하는 문제

(단 , 시간복잡도가 O(N)이어야 하며, for, while 등의 반복문은 사용하면 안된다.)

입출력 예시

피보나치 수열의 0번째 요소는 0으로 정의하며 이에 따른 수열은 다음과 같다.
0 1 1 2 3 5 8 13 21....

내가 작성한 코드

const cache = [];

function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.

  //0번째와 1번째 피보나치 수는 1이다
  //첫번째 base case: 2번째 수부터는 바로 직전의 두 피보나치 수의 합으로 정의한다.
  if(n <= 1){
    cache[n] = n; //0과 1은 캐시에 저장해놓고 바로 리턴 가능. 
    return n;
  }
  //n번째 피보나치 수를 이전에 이미 구했다면 두번째 base case에 넣어버린다
  //이미 피보나치 수를 구했다는 것은 어떻게 알수있을까?
  //배열에다가 저장을할까? 
  //피보나치 수를 구해서 자장하는 배열을 만들자. 이것을 cache라고 부른다. 
  //입력에 n이 들어왔을때 이미 캐시 배열에 존재하는 거라면, 그 배열에서 찾아낸다
  if(cache[n] !== undefined){
    return cache[n];
  }
  // recursive step : n번째 피보나치 수를 이전에 구한 적이 없다면 아래의 공식을 이용한다
  cache[n] = fibonacci(n - 2) + fibonacci(n - 1);
  return cache[n];

  //기존 알고리즘 문제점: 같은 값을 얻기 위해 함수를 여러번호출해야한다.
	//이미 구해놓은 피보나치 수는 다른 곳에 따로 저장을 해놓고 필요할때 꺼내쓰는 것이 더 효율적이다.
  //해결책 링크 : <https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95.html>
}