재귀

재귀는 어떤 문제를 작은 단위의 동일한 문제들로 나누어 해결하는 방법으로, 함수 자기 자신을 다시 호출하는 것이 특징이다.

재귀 함수는 무한 루프에 빠지는 것을 막기 위해 재귀 함수를 멈추는 조건이 반드시 필요하다.

자바스크립트에서 호출 스택 크기의 한계

재귀 호출의 한계량은 브라우저 마다 다르다.

피보나치 수열

피보나치 수열의 수학적 정의는 다음과 같다.

1. 1항, 2항은 1이다.

2. n(n > 2)항은 (n - 1)항과 (n - 2)항의 합이다.

function fibonacci(num) {
  if (num === 1 || num === 2) {
    return 1;
  }
  return fibonacci(num - 1) + fibonacci(num - 2);
}

재귀가 아닌 방식으로 작성하면

function fib(num) {
  var n1 = 1,
    n2 = 1,
    n = 1;
  for (var i = 3; i <= num; i++) {
    n = n1 + n2;
    n1 = n2;
    n2 = n;
  }
  return n;
}

재귀가 항상 빠른건 아니다 하지만 코드가 좀 더 명료하게 이해가 되고 코딩이 줄어드는 이점은 있다.

동적 프로그래밍

동적 프로그래밍은 복잡한 문제를 작은 하위 문제들로 나누어 푸는 최적화 기법이다.

피보나치 수열도 동적 프로그래밍의 일환이다.

동적 프로그래밍을 사용해 문제를 해결할 때 중요한 세 단계가 있다.

1. 하위 문제들을 정의한다.

2. 하위 문제들을 풀기 위한 재귀를 구현한다.

3. 베이스 케이스를 찾는다.

최소 동전 교환 문제

주어진 금액을 동전 d1,d2, ... d으로 바꿔줄 때 필요한 동전의 최소 개수를 찾는 문제다.

예를들어 미국에는 1,5,10,25센트짜리 동전이 있다.

36센트를 바꾼다면 25센트 하나 10센트 1개 1센트 1개가 정답이다.

이 문제를 어떻게 알고리즘화 할 수 있다.

최소 동전 교환 문제의 목적은 금액 n을 나타내는 동전의 조합 중 개수를 최소로 하는 경우를 찾는 것이다.

그렇게 하려면 먼저 모든 x < n에 대한 해를 찾아야 한다.

그러고 나서 더 적은 금액의 동전에 대한 해을 바탕을 최적화된 해를 찾는다.

function MinCoinChange(coins) {
  var coins = coins;
  var cache = {};
  this.makeChange = function(amount) {
    var me = this;
    if (!amount) {
      return [];
    }
    if (cache[amount]) {
      return cache[amount];
    }
    var min = [],
      newMin,
      newAmount;
    for (var i = 0; i < coins.length; i++) {
      var coin = coins[i];
      newAmount = amount - coin;
      if (newAmount > 0) {
        newMin = me.makeChange(newAmount);
      }
      if (
        newAmount >= 0 &&
        (newMin.length < min.length - 1 || !min.length) &&
        (newMin.length || !newAmount)
      ) {
        min = [coin].concat(newMin);
        console.log(`new Min ${min} for ${amount}`);
      }
    }
    return (cache[amount] = min);
  };
}

makeChange 메서드는 재귀 호출하면서 실제로 문제를 푼다.

newAmount 가 유효한지 최적의 newMin이 나왔는지 newMin과 newAmount 가 모두 유효한지 세가지 조건을 체크하고 모두 충족한다면 이전보다 더 나은 결과를 얻었다는 반증이다.

욕심쟁이 알고리즘

욕심쟁이 알고리즘은 전역 최적해를 찾이 위해 각 단계마다 지역 최적해를 선택해 문제를 해결하는 방법이다.

최소 동전 교환 문제

function MinCoinChange(coins) {
  var coins = coins;
  this.makeChange = function(amount) {
    var change = [],
      total = 0;
    for (var i = coins.length; i >= 0; i--) {
      var coin = coins[i];
      while (total + coin <= amount) {
        change.push(coin);
        total += coint;
      }
    }
    return change;
  };
}

욕심쟁이 알고리즘은 동적 프로그래밍 알고리즘 보다 더 간단하고 빠르긴 하지만 항상 최적의 답을 내놓지는 않는다.

하지만 평균적으로 수행 시간에 비해 만족할만한 결과를 내놓는다.