재귀(recursion)와 메모이제이션(Memoization)

오늘은 프리코스에서 이머시브로 넘어가는 과정 중에 진행했던 hiring assessment를 페어분과 함께 복습하는 시간을 가질 수 있었다. 그런데 내가 푼 방식이랑 페어분이 푼 방식이 달라 의문을 가졌는데 메모이제이션이라는 것을 들을 수 있었다.

---

✅ 재귀(recursion)란?

자기자신을 호출하는 함수

 

✅ 메모이제이션(Memoization)란?

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

 

---

바로 예시를 보자면 문제는 다음과 같았다.

 

 

코드스테이츠 HA문제

---

나의 경우

function test6() {
  // 호출 될 때마다 다음 피보나치 수를 리턴하고 카운트를 저장한다.
  let count = 0;
  // 피보나치 수열 함수
  function fibonacci(num) {
    return num <= 1 ? num : fibonacci(num-2) + fibonacci(num-1);
  }

  // test6 함수를 실행하면 이 함수가 반환
  // 실행할 때마다 클로저가 count를 1씩 증가시키고 피보나치 수열 값 반환
  // count가 증가하고 피보나치 함수가 리턴되기 때문에 0부터 시작하기 위해서 -1
  return function() {
    count++;
    return fibonacci(count-1);
  }
}

 

페어분의 경우

function test6() {
  test6.cnt = 0;
  return () => {
    if(test6[test6.cnt] !== undefined){
      test6.cnt++;
      return test6[test6.cnt - 1];
    }

    if(test6.cnt < 2){
      test6[test6.cnt] = test6.cnt;
    }
    else{
      test6[test6.cnt] = test6[test6.cnt - 1] + test6[test6.cnt - 2];
    }

    test6.cnt++;
    return test6[test6.cnt - 1];
  }
}

 

처음엔 내 코드가 짧아서 자신감이 뿜뿜했었다.(사실 페어분은 엄청난 고수셨다..!) 그런데 이 메모이제이션 기법을 사용하면, 특히 피보나치 수열같은 같은 경우는 반복되는 계산이 점점 기하급수적으로 많아지기 때문에 엄청난 효과를 볼 수 있다고 했다.

 

나의 경우는 몇번이고 계속 계산을 반복한다면, 페어분의 경우는 이미 계산된 값을 따로 저장해놓고 이 값을 다시 쓰기 때문에 초반에는 차이가 미미하지만 후반으로 갈 수록 계산 속도의 차이가 엄청나다고 한다.