문제

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

0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

입력

인자 1 : n
number 타입의 n (n은 0 이상의 정수)

출력

number 타입을 리턴해야합니다.

주의사항

재귀함수를 이용해 구현해야 합니다.
반복문(for, while) 사용은 금지됩니다.
함수 fibonacci가 반드시 재귀함수일 필요는 없습니다.

입출력 예시

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))이 존재합니다. 재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.

풀이

function fibonacci(n){ 
//재귀로 사용할 때 이미 불러온 값들을 기억하지 못해서 너무 많이 부른다 
//그러므로 배열에 저장해서 배열에서 값을 불러온다 
//문제 : 배열이 갱신된다 
//해결 : 재귀함수 밖에 배열을 선언 
//- 즉 피보나치 함수 안에 다른 함수로 재귀 사용

const arr = [0,1];//배열 선언

function fibo(n){ 

if(arr[n] !== undefined){ 
	return arr[n];//이미 있는 값 불러온다
}
arr[n] = arr[n-1] + arr[n-2]; //재귀, 배열에 추가
return arr[n];
}

return fibo(n);
}