22_fibonacci

function fibonacci(n) {
  // Q. 피보나치 수열 중 n 번째 항의 수를 리턴
  // ! 재귀함수를 이용해 구현
  // fibonacci(0) --> 0, fibonacci(1) --->1
  // fibonacci(2) --> fibonacci(0) + fibanacci(1) ---> 1
  // fibonacci(3) ---> fibaonacci(2) + fibaonacci(1) ---> 1 + 1 --> 2
  // finobacci(4) ---> fibaonacci(3) + fibaonacci(2) ---> 2 + 1 --> 3
  // fibonacci(5) ---> fibaonacci(4) +  fibaonacci(3) ---> 3 + 2 --> 5 
  // fibaonacci(n) = fibaonacci(n-1) + fibaonacci(n-2)

  if(n === 0){ return 0 }
  if(n < 2){ return 1 }
    return fibonacci(n-1) + fibonacci(n-2)

}

Dynamic with memorization : 0(N)

이미 해결한 문제의 정답을 따로 기록해 주고, 다시 해결하지 않는 기법

동일한 문제가 중복으로 계산되는 것이 보임

let fibonacci = function (n) {
  const memo = [0, 1];
  const aux = (n) => {
    // 이미 해결한 적이 있으면, 메모해둔 정답을 리턴한다.
    if (memo[n] !== undefined) return memo[n];
    // 새롭게 풀어야하는 경우, 문제를 풀고 메모해둔다.
    memo[n] = aux(n - 1) + aux(n - 2);
    return memo[n];
  };
  return aux(n);
};