[JS] fibonacci

입력

인자: n

Number타입의 0이상의 정수 n

출력

0번째 수가 0이고 1번째 부터 피보나치 수를 갖는 수열의 n번째 수

주의사항

• 재귀함수를 이용해 구현해야 한다.
• 반복문(for, while) 사용은 금지된다.

피보나치 수열

처음 두 항을 1과 1로 한 후, 그 다름 항부터는 바로 앞의 두 개의 항을 더해 만드는 수열.

1, 1, 2, 3, 5, 8, 13, 21, ...

수도코드

두개의 항을 더해야하기때문에 0,1을 담은 배열을 만든다.
let arr = [0, 1]

배열을 피보나치수열로 만들 함수를 n길이만큼 재귀 시키위해 변수 count를 만든다.
let count = 2

배열을 피보나치수열로 만들 재귀함수를 만든다.
let makeFibonacciArr = (arr) => {return makeFibonacciArr (arr)}

재귀의 base case는 arr의 n번째 요소가 0,1일 경우와 수가 있을 경우 arr을 리턴
if(arr[n] <= 1 || arr[n] !== undefined) return arr

재귀의 recursive Case는 arr의 전전 요소와 전 요소의 합을 현재요소에 할당
arr[count] = arr[count - 2] + arr[count - 1]

n길이 만큼 피보나치 수열을 담은 배열의 n번째 요소를 리턴
let fibonacciArr = makeFibonacciArr(arr)
return fibonacciArr[n]

코드

function fibonacci(n) {
  let arr = [0, 1];
  let count = 2;
  let makeFibonacciArr = (arr) => {
    if(arr[n] <= 1 || arr[n] !== undefined) {
      return arr;
    }
    arr[count] = arr[count - 2] + arr[count - 1];
    count ++
    return makeFibonacciArr(arr);
  }
  let fibonacciArr = makeFibonacciArr(arr);
  return fibonacciArr[n];
}