Toy 2 피보나치

CALL STACK

// fib(3) = fib(2) + fib(1) = 1 + 1 = 2
// fib(4) = fib(3) + fib(2) = 2 + 1 = 3
// fib(5) = fib(4) + fib(3) = 3 + fib(3)

기존코드

기존 코드로 구현시 디버깅 해보면 알겠지만 위의 예시에서는 fib(3)이 총 2번 호출 된다.
콜스택상에서 fib(3)의 메모리가 사라져서 다시 호출해야 되기 때문이다.
입력값 n 이 커질수록 무수히 많은 콜스택이 반복되어 져야 하기 때문에 다른 접근 방법이 필요했다.

function fib(n) {
  if (n < 3) return 1;
  return fib(n - 2) + fib(n - 1);
}

naive solution: O(2^N)

 let fibonacci = function (n) {
 if (n <= 1) return n;
 return fibonacci(n - 1) + fibonacci(n - 2);
 };

fibo(10)
= fibo(9) + fibo(8)
= fibo(8) + fibo(7) + fibo(7) + fibo(6)
여기까지만 보아도 동일한 문제가 중복으로 계산되는 것을 알 수 있다.

새로 구현한 코드

function fibonacci(n) {
  // n = 5
  if (n === 0) return 0;
  if (n < 3) return 1;
  let prev = 1;
  let curr = 1;

  for (let i = 2; i < n; i++) {
    // i = 2 i = 3 i = 4
    const next = prev + curr; // next = 2 next = 3 next = 5
    prev = curr; // prev = 1 prev = 2 prev = 3
    curr = next; // curr = 2 curr = 3 curr = 5
  }
  return curr; // 5
}

아래는 레퍼런스 코드
dynamic with meoization: O(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);
};

🔑 콜스택에 대한 이해와 같은 함수를 호출하지 않기 위해 데이터를 저장해두는 방식 . 기억하자!
차근차근 자료구조 공부를 해나가면서 열심히 정리할 것!