ZeroCho Blog

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

재귀

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

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)을 해보세요. 사소한 차이가 결과에 엄청난 영향을 미칩니다. 프로그래머라면 꼭 기억해두어야겠죠?

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