문제

아래와 같이 정의된 피보나치 수열 중 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))이 존재합니다. 재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.

---

접근방식

내가 알고있던 피보나치 알고리즘은 n은 이전 두 수의 합이 된다는 것이다. 식으로 표현해보면 n= (n-2) + (n-1)
결국 (n-2)도 이전 두 수의 합이고, (n-1)도 이전 두 수의 합으로 이루어진 값이니 작은 단위로 쪼개 계산하는 재귀함수로 접근해서 풀 수 있었다.

//피보나치
//n=0 > 0
//n=1 > 1
//n=2 > 1 - (n=0) + (n=1)
//n=3 > 2 - (n=1) + (n=2)
//n=4 > 3 - (n=2) + (n=3)
//n=5 > 5 - (n=3) + (n=4)
//n=6 > 8 - (n=4) + (n=5)

그런데 기존 알고리즘의 시간복잡도는 O(2n)인데 O(N)의 방법이 있다고?

흠.. 기존 알고리즘은 예를 들어 n=4일 때 값을 구한다고 하면 4는 3일 때 값과 2일 때 값의 합이고, n=3은 2일 때 값과 1일 때 값의 합이다. 이 때 문제점을 발견하였나?
n=4일 때 3의 값은 n=3일 때 구했음에도 불구하고 재귀로 한번 더 돌아간다는 것이다.
이 전에 구했던 값이 저장되지 않고, 초기화되기 때문에 계속 재귀로 구해야 하므로 시간이 더 오래걸린다.

그렇다면 재귀를 돌아 구했던 값을 저장해놓으면 어느 한 곳에 저장해놓고 가져다 쓸 수 있지 않을까? >>> memorization!!

한번 구한 값은 memo라는 배열에 값을 저장해놓고, 다음번에 같은 값을 요구한다면 memo 배열에 저장된 값을 쓴다면 재귀를 굳이 돌지 않아도 된다.

제출 코드

function fibonacci (n) {
  let memo = [0, 1, 1] 
	
  //재귀를 돌아 이미 값이 저장되있을 땐 값을 리턴한다.
  if(memo[n] !== undefined) return memo[n]

  let fibo = fibonacci(n-2) + fibonacci(n-1) 
  //값을 저장
  memo[n] = fibo

  return fibo
	
}