[Development] Recursion과 memoization

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

일반적인 피보나치수열은 재귀함수로 쉽게 구할수가 있다.
하지만 구하려는 n의 값이 30만 넘어가도 함수실행이 엄청나다.

피보나치수열은 함수가 실행될때 중복되는값이 매우 많기 때문에 불필요한 연산을 굉장히 많이 하게 된다. 따라서 중복되는값을 따로 저장해서 같은 값을 연산하면 저장한곳에서 주면 효율성이 엄청나게 올라간다.

const fibWithMemo = n => {
  const cache = {};
  const fibRecur = m => {
    if (m < 2) {
      cache[m] ? m : (cache[m] = m);
      return cache[m];
    } else {
      cache[m] ? m : (cache[m] = fibRecur(m - 2) + fibRecur(m - 1));
      return cache[m];
    }
  };
  return fibRecur(n);
};

값이 cache에 없으면 그 값들을 하나씩 저장하고 cache에 해당 값이 있으면 사용하는방식이다.

 

memoization하지 않은 피보나치

n의 값이 42일때 5100ms나온다. 매우 느리다.

yes memoization

n=100일때의 성능은 10ms이다.

체감이 확되니까

이래서 자료구조를 배우나 싶기도 하다.