메모이제이션 Memoization

메모이제이션이란 프로그래밍을 할 때 반복되는 결과를 메모리에 저장해서 다음에 같은 결과가 나올 때 빨리 실행하는 코딩 기법을 말한다.

클로저를 사용해서 유지되는 저장공간을 이용해 함수를 반복적으로 수행할 때 함수 내부의 실행횟수를 줄일 수 있다.

메모이제이션을 사용해서 팩토리얼 함수 구현

let factorial = (function() {
  let save = {};
  let fact = function(number) {
    if (number > 0) {
      let saved = save[number - 1] || fact(number - 1);
      let result = number * saved;
      save[number] = result;
      console.log(saved, result);
      return result;
    } else {
      return 1;
    }
  };
  return fact;
})();

factorial(7); // 1 1, 1 2, 2 6, 6 24, 24 120, 120 720, 720 5040
factorial(7); // 720 5040-

IIFE로 리턴된 fact()를 factorial()에 담았다.
saved 변수에는 지속적으로 fact()에 number를 하나씩 줄인 값이 들어가게 된다.

최종적으로 saved에는 factorial(num-1)의 값이 들어있으며
마지막 줄에 console창에 출력된 것처럼
factorial(7)을 했을 때 saved 변수에는 factorial(6)의 값이 들어있으므로
실행 횟수가 2회로 줄어들게 된다.

메모이제이션을 사용해서 피보나치 수열 함수 구현

방법 1

let fibonacci = (function() {
  let save = {};
  let fibo = function(number) {
    if (number < 2) {
      return number;
    } else {
      let saved1 = save[number - 1] || fibo(number - 1);
      let saved2 = save[number - 2] || fibo(number - 2);
      let result = saved1 + saved2;
      save[number] = result;
      console.log(saved1, saved2, result);
      return result;
    }
  };
  return fibo;
})();

fibonacci(5); // 1 0 1, 1 1 2, 2 1 3, 3 2 5, 5
fibonacci(5); // 3 2 5, 5

마찬가지로 saved1, saved2 에 fibo()에 현재 number값의 전, 전전 값이 전달된 결과값이 담긴다.

따라서, 마지막줄에서 보듯이 같은 인자를 전달해서 함수를 두번 호출했을 때
두번째 호출에서는 내부함수의 실행횟수가 2번으로 줄어드는것을 볼 수 있다.

출처 : www.zerocho.com/category/JavaScript/post/579248728241b6f43951af19

방법 2

let memorized = [0, 1];
let fibonacci = function (n) {
  if (memorized[n] !== undefined) return memo[n];
  memorized[n] = fibonacci(n - 1) + fibonacci(n - 2);
  return memorized[n];
};

이렇게 하면 memorized 라는 배열에 재귀함수로 한번 값을 알고있는 n번째 피보나치 수열값은 저장이 된다.
규칙성이 없는 1번째, 2번째 값인 0과 1은 디폴트로 넣어준다.
방법 1은 객체를 사용했다면 방법 2는 배열을 사용했다.