[JS] Memoization

재귀함수를 활용하면서도 메모리를 효율적으로 사용하려면 Memoization 기법을 사용하면 된다.

Memoization

메모이제이션(memoization)이란 프로그래밍을 할 때 반복되는 결과를 메모리에 저장함으로써 이후 같은 결과가 사용될 때 저장한 값을 이용해 빠르게 실행하는 코딩 기법을 말한다.

Memoization 활용

재귀(recursion)와 메모이제이션(memoization)을 활용하여 피보나치 수열의 num 번째 숫자를 반환하는 함수를 작성해보았다.

let callCount = 0; // 연산 횟수

function fiboByMemoization(num, memo) {
  callCount++; // 연산 횟수 +1
  memo = memo || [];
  
  if(memo[num] !== undefined) {
    return memo[num];
  }  
  
  if(num <= 1) {
    memo[num] = num;
    return num;
  }
  
  memo[num] = fiboByMemoization(num - 2, memo) + fiboByMemoization(num - 1, memo);
  
  return memo[num];
}

fiboByMemoization(10);
console.log(callCount); // 19

재귀를 활용했음에도 불구하고 callCount 값이 19 로 그 크기가 작다.
이처럼, Memoization 기법을 활용하면 재귀함수의 메모리 사용량을 효율적으로 낮출 수 있다.