[JS] memoization을 이용한 피보나치 수열 함수 구현

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

오늘은 재귀함수에서 한번 구해놓은 값을 저장하는 기법인 memoization을 이용하여 피보나치 수열의 n번째 항의 값을 반환하는 함수를 구현해보도록 하겠습니다.

(이때 n은 0부터 시작하므로, 사용시 주의해주세요.)

const fiboRecMemoized = (() => {
  // 계산 결과를 저장하는 저장소를 만듭니다.
  const memo = new Map();

  const fiboRec = n => {
    // 만약에 이전에 같은 인수로 계산한 적이 있다면
    // 해당 결과를 바로 반환합니다.
    let result = memo.get(n);
    if (result != undefined) return result;

    result = (
      n < 1 ? 0 :
      n === 1 ? 1 :
      fiboRec(n - 1) + fiboRec(n - 2)
    );

    // 계산 결과를 저장소에 저장한 후 반환합니다.
    memo.set(n, result);
    return result;
  }

  return fiboRec;
})();