이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌35 - JavaScript - 2년 전 등록

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