게시글

강좌35 - JavaScript - 3년 전 등록

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

조회수:
0

안녕하세요. 이번 시간에는 재귀메모이제이션에 대해 알아보겠습니다.

재귀

재귀란 함수가 자기 자신을 호출하는 것을 의미합니다. 간단하게 팩토리얼(!)을 알려주는 함수를 만들어볼까요?

var factorial = function(number) {
  var result = 1;
  for (var i = 1; i <= number; i++) {
    result *= i;
  }
  return result;
};
factorial(3); // 6
factorial(4); // 24

물론 위의 코드도 맞는 코드지만 우아하지도 않고 확장가능성도 없습니다. 이번 시간에 배울 재귀를 사용해서 코드를 만들어보겠습니다.

var factorial = function(number) {
  if (number > 0) {
    return number * factorial(number - 1);
  } else {
    return 1;
  }
};
factorial(3); // 6
factorial(4); // 24

factorial 함수를 만들었는데 그 안에 factorial 함수를 또 호출합니다. 자기 자신을 호출하는 건데요. 인자만 n에서 n-1로 바뀌었습니다. factorial(3)을 호출하면 내부적으로는 3 * factorial(2)가 호출됩니다. factorial(2)2 * factorial(1)을 호출하고요. factorial(1)1 * factorial(0)을 호출합니다. factorial(0)==1이기때문에 최종적으로 결과는 3 * 2 * 1 * 1 = 6이 됩니다.

참고로 처음 코드처럼 한 번에 풀지 않고, 재귀적으로 푸는 것은 분할 정복 알고리즘 중의 하나입니다. 어떤 문제를 한 번에 풀기 힘들 때, 작은 조각으로 쪼개어 푸는 것을 분할 정복 알고리즘이라고 합니다.

이렇게 재귀를 사용하는 것은 컴퓨터에게는 많은 부담을 주지만, 사람에게는 가독성을 높혀 줍니다. 따라서 성능을 중시한다면 재귀를 쓰지 않는 게 좋습니다. 하지만 재귀는 많은 곳에서 사용되기 때문에 꼭 알아두셔야 합니다. 다음으로는 재귀를 사용할 때 자주 쓰이는 코딩 기법을 소개합니다.

메모이제이션

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

이전 코드에서 factorial(3)을 호출한 후 factorial(4)를 할 때 뭔가 아쉽습니다. factorial(4)4 * factorial(3)인데요. factorial(3)은 아까 호출했었죠. 하지만 factorial(4)에서 예전의 결과값을 활용하지 못하고 다시 계산해버렸습니다. 만약 factorial(3)을 했던 결과값이 메모리에 남아있었다면 재사용할 수 있었겠죠?

다음과 같이 클로저를 사용해 계속 유지되는 저장 공간을 만든 후 코드를 바꿔봅시다.

var factorial = (function() {
  var save = {};
  var fact = function(number) {
    if (number > 0) {
      var saved = save[number - 1] || fact(number - 1);
      var 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-

이렇게 클로저를 만든 후 factorial(7)을 두 번 연속 해봤습니다. 처음 호출 때는 처음 계산하는 것이기 때문에 계산이 여러 번 실행됩니다. console에 나오는 게 계산을 실행하는 과정입니다. 두 번째 호출 때는 한 번 만에 실행 결과가 나옵니다. 이전에 했던 계산이 메모리에 저장되어있기 때문이죠.

다른 예제로 피보나치 수열이 있습니다. 피보나치 수열은 특이하게도 함수 안에서 두 번의 재귀 호출을 합니다. 재귀가 빛을 발하는 순간이죠.

var fibonacci = function(number) {
  if (number < 2) {
    return number;
  } else {
    return fibonacci(number - 1) + fibonacci(number - 2);
  }
};

이것도 클로저를 사용해 메모이제이션합시다.

var fibonacci = (function() {
  var save = {};
  var fibo = function(number) {
    if (number < 2) {
      return number;
    } else {
      var saved1 = save[number - 1] || fibo(number - 1);
      var saved2 = save[number - 2] || fibo(number - 2);
      var 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

역시 클로저를 만든 후 fibonacci(5)를 두 번 연속 호출했습니다. 처음 호출 때는 결과들을 저장하느라 계산이 여러 번 실행되지만 두 번째 호출에는 이전 결과를 불러와서 한 번에 결과가 나옵니다.

메모이제이션은 반복되는 계산이 많을수록 효과가 높아집니다. 특히 반복 작업이 많을 경우에는, 숫자가 커질수록 반복 횟수가 기하급수적으로 늘어납니다. 메모이제이션을 사용하지 않은 코드로 한 번 fibonacci(40)을 해보세요. 얼마나 많은 반복이 일어나는지 바로 알 수 있습니다. 그리고 메모이제이션을 사용한 코드로 fibonacci(40)을 해보세요. 사소한 차이가 결과에 엄청난 영향을 미칩니다. 프로그래머라면 꼭 기억해두어야겠죠?

이제까지는 언어에 대해 배웠으니 다음 시간부터는 실제로 어떻게 사용할 수 있는지 디자인 패턴을 알아보겠습니다.

투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

5개의 댓글이 있습니다.
2년 전
메모이제이션 설명부분에 factorial 함수는 ieff니까 호출해야하는 함수는 fact아닌가요..? 아직 초보자라 잘 모르겠네요..
2년 전
IIFE로 return된 fact함수가 factorial에 담기는 겁니다. factorial을 사용하는 게 맞습니다
2년 전
요즘 컴파일러와 언어의 내부 알고리듬의 성능이 좋아져서 자체적으로 옵티마이제이션을 해주기 때문에 리커시브를 쓴다고 해서 예전처럼 퍼포먼스에 커다란 차이를 보이지는 않는다고 합니다.
2년 전
사파리를 제외하고는 브라우저에서 꼬리 재귀를 지원하지 않기도 하고요. 브라우저에서는 맥시멈 콜 스택이 한정되어 있다는 게 문제겠지요 ㅠ
3년 전
너무 어렵네요 ㅠ 메모이제이션에서 factorial(7);을 했을 때 처음에 1, 1이 어떻게 나오는지 계산순서를 감을 못잡으니 도저히 이해가 안되네요 ㅠ
3년 전
var saved = save[number - 1] || fact(number - 1); << 이게 무슨의미인지 알수있을까요??? 아무리 봐도 자세히 모르겠어서 질문드렸습니다 ㅎㅎ
3년 전
save는 이전 계산 결과를 저장하는 곳입니다. 이전에 계산한 결과가 있으면 그걸 사용하고 없으면 새로 계산하라는 뜻입니다.
3년 전
아~ 그런 의미군요 ㅎㅎ 늦은밤중에도 감사합니다 ㅎㅎ
3년 전
만약에 factorial()을 실행할때마다 var save = {}가 실행된다면 매번 초기화되지 않을까요? 반대로 말해서 만약 메모이제이션된 값을 가비지콜렉션하는 메서드를 만드려고 하는데 var save = {}가 소용이 없다면 어떻게 해야할까요?
어떻게 비공개 변수가 초기화되지 않고 남아있는건지 궁금합니다.
3년 전
잘 보셔야 할 게 factorial은 즉시 실행 함수(IIFE)라서 return 값인 fact 함수와 같습니다. factorial 공간은 클로저가 되는 거고요. save 변수는 계속 유지됩니다. 따라서 save 변수는 매번 초기화되지 않습니다.
3년 전
헷갈릴 여지가 있는 코드가 있어 조금 수정했습니다. 메모이제이션된 값을 가비지콜렉션하려면 IIFE가 아니라 생성자를 통해 객체를 만들어야할 거 같습니다. 코드를 포함한 내용은 지식인이나 메일을 통해 질문해주세요!
3년 전
뭔가 알것 같네요 답변 감사합니다!