fibonacci [부트캠프 알고리즘22]

fibonacci

문제
-> 피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
위와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴하라.

입력
-> number 타입의 n (n은 0 이상의 정수)

출력
-> number 타입을 리턴하라.

주의사항
-> 재귀함수를 이용해 구현해야 한다.
반복문(for, while) 사용은 금지!
함수 fibonacci가 반드시 재귀함수일 필요는 없다.

입출력 예시

// 입출력 예시
fibonacci(0);
-> 0
fibonacci(1);
-> 1
fibonacci(5);
-> 5
fibonacci(9);
-> 34

의사코드

// fibonacci() 함수를 재귀함수로 만들면 실행시간 초과로 나오므로 내부에 함수를 만들고 그 함수를 재귀함수로 만들자

코드작성

function fibonacci(n) {

  let arr = [0,1]; // 피보나치 수열의 0번째 1번째 항을 만들어준다.
  const fibo = (num = 2) => { // 인자의 초기값을 2로 할당
    arr.push(arr[num - 1] + arr[num - 2]); // 바깥에 선언한 arr에 push해준다. 
    if(n <= num){
      return; // base case 로 재귀탈출 -> 쓰지 않으면 영원히 반복 -> 전체적으로 보면 while문 처럼 사용한것이다.
    }
    fibo(num + 1); // n <= num이 성립되지않으면 fibo(num + 1) 로 재귀실행 시켜준다.
  }
  fibo(); // fibo함수를 실행시켜준다.
  return arr[n]; // fibo함수가 종료되는 시점의 arr의 n 번째요소를 리턴!
}