[알고리즘] 피보나치(fibonacci)

문제

아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.

• 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.

• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

• 재귀함수를 이용해 구현해야 합니다.

• 반복문(for, while) 사용은 금지됩니다.

입출력 예시

let output = fibonacci(0);
console.log(output); // --> 0

output = fibonacci(1);
console.log(output); // --> 1

output = fibonacci(5);
console.log(output); // --> 5

output = fibonacci(9);
console.log(output); // --> 34


** Advanced

피보나치 수열을 구하는 효율적인 알고리즘(`O(N)`)이 존재합니다. 재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.

풀이

지난 알고리즘 가위바위보에서 사용했던 재귀 방식을 여기 이 알고리즘에게도 적용시켜 구현해보았다.
recursion의 파라미터에 count를 정의를 한 후 다시 재귀를 돌 때마다 바로바로 적용부터 한 후 재귀를 실행하게 하였다.

function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.
  let arr = [0, 1];

  const recursion = (count = 2) => {
    arr.push(arr[count-2] + arr[count-1]);

    if(count === n) {
      return;
    }

    recursion(count + 1);
  }
  
  if(n === 0) {
    return 0;
  }
  else if(n === 1) {
    return 1;
  }
  else {
    recursion();
    return arr[n];
  }
}