11장 재귀적으로 작성하는 법

재귀적으로 작성하는 법을 보다 쉽게 익힐 수 있는 기법을 소개한다.

11.1 재귀 카테고리: 반복 실행

반복적으로 한 작업을 실행하는 알고리즘에 재귀 함수를 적용할 수 있다.

이전에 다뤘던 카운트다운 함수를 예시로 들 수 있다.

function countdown(number) {
  console.log(number);

  if (number === 0) {
    return;
  } else {
    countdown(number - 1);
  }
}

반복 실행 카테고리에 속하는 문제들은 함수의 마지막 줄에서 단순히 그 함수를 다시 한 번 호출한다. 위의 예제에선 countdown(number - 1)이다.

11.1.1 재귀 트릭: 추가 인자 넘기기

숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 작성하려고 한다. 단, 새 배열을 만들어선 안 되고 배열 자체에서 수정해야 한다.

function doubleArray(array, index) {
  if (index >= array.length) {
    return;
  }

  array[index] *= 2;
  doubleArray(array, index + 1);
}

const array = [1, 2, 3, 4];
doubleArray(array, 0);

console.log(array);		// [2, 4, 6, 8]

배열 내 각 숫자의 인덱스를 기록하고 증가하기 위해 함수의 인자로 index를 추가로 전달한다.

function doubleArray(array, index = 0) {
  if (index >= array.length) {
    return;
  }

  array[index] *= 2;
  doubleArray(array, index + 1);
}

const array = [1,2,3,4]
doubleArray(array)

console.log(array);		// [2, 4, 6, 8]

인자 index는 항상 0부터 시작해야 한다. 이 때 인자의 기본값으로 0을 할당해주면 함수를 처음 호출할 때 인덱스 인자를 전달하지 않아도 된다.

11.2 재귀 카테고리: 계산

재귀가 유용하게 쓰이는 또 하나의 영역은 하위 문제의 계산 결과에 기반해 계산할 수 있을 때다.

이전에 다뤘던 팩토리얼 함수가 예시이다.
팩토리얼 함수를 구현할 때는 1부터 n까지 순차적으로 곱하는 전형적인 반복문을 사용할 수도 있다.

function factorial(n) {
  let product = 1;

  for (let i = 1; i <= n; i++) {
    product *= i;
  }

  return product;
}

반복문이 아니라 하위 문제에 기반해 팩토리얼을 계산할 수 있다.
하위 문제는 입력을 더 작게 한 똑같은 문제다.

factorial(6) = 6 * factorial(5)이다. 즉 factorial(5)의 리턴값을 알면 그 값에 6을 곱해 factorial(6)을 구할 수 있다.

이 때, factorial(5)는 factorial(6)을 계산하기 위해 쓰이는 더 작은 문제이므로 factorial(6)의 하위 문제이다.

function factorial(number) {
  if (number === 1) {
    return 1;
  } else {
    return number * factorial(number - 1);
  }
}

11.2.1 두 가지 계산 방식

계산 함수를 작성하는 방식은 상향식(bottom-up), 하향식(top-down)으로 두 가지다.

두 방식 모두 재귀로 가능하다. 11.2에서 반복문을 통해 구현한 상향식 방식을 재귀로 구현할 수 있다.

function factorial(n, i = 1, product = 1) {
  if (i > n) {
    return product;
  }
  return factorial(n, i + 1, product * i);
}

구하려는 팩토리얼 수인 n과, 함수가 호출될 때마다 증가하는 i, 수를 곱한 결과를 저장하는 product를 인자로 전달해야 한다.

재귀로 상향식 방식을 구현할 수 있으나 그다지 간결하지 못하며 반복문에 비해 특별한 장점이 없다. 상향식에서는 반복문이든 재귀든 계산 방식이 같다.

하지만 하향식을 구현할 방법은 재귀뿐이다.

11.3 하향식 재귀: 새로운 사고방식

재귀는 하향식 방식을 구현하는 데 탁월하고, 하향식 사고방식은 문제를 해결하는 새로운 사고 전략을 제공한다.

하향식으로 풀어 나갈 때는 문제의 본질에 세부적으로 파고들지 않아도 된다.

return number * factorial(number - 1)을 작성할 때, factorial(number -1)이 어떻게 작동하는지 모르더라도 그 함수가 올바른 값을 반환하리라 가정한다. 세부 사항은 하위 문제에서 다루면 된다.

11.3.1 하향식 사고 절차

1. 작성 중인 함수를 이미 누군가 구현해 놓았다고 상상하자.
2. 문제의 하위 문제를 찾자.
3. 하위 문제에 함수를 호출하면 어떻게 되는지 보고 거기서부터 시작하자.

11.3.2 배열 합

주어진 배열 [1, 2, 3, 4, 5] 내 모든 수를 합하는 sum 함수를 작성한다.

가장 먼저, sum 함수가 이미 구현되어 있고, 잘 작동한다고 가정한다.

다음으로 하위 문제를 찾는다. 여기서 하위 문제는 첫 번째 원소를 제외한 [2, 3, 4, 5]다.

마지막으로 하위 문제에 함수를 호출하면 어떻게 되는지 본다. sum 함수는 이미 잘 작동한다고 가정하므로, sum([2, 3, 4, 5])를 호출하면 14가 나온다. 그 결과에 1만 더하면 된다.

수도 코드로 작성하면 다음과 같다.

return array[0] + sum(배열에_남아있는_수)

이를 자바스크립트 코드로 옮기면 다음과 같다.

return array[0] + sum(array.slice(1))

기저조건을 생략하고 sum 함수를 작성하면 다음과 같다.

function sum(array) {
  return array[0] + sum(array.slice(1));
}

끝으로 기저 조건을 추가해서 처리한다.

function sum(array) {
  if (array.length === 1) {
    return array[0];
  }

  return array[0] + sum(array.slice(1));
}

11.3.3 문자열 뒤집기

문자열을 뒤집는 reverse 함수를 작성한다. "abcde"를 받으면 "edcba"로 반환한다.

함수가 이미 구현되어 있다고 가정하고, 하위 문제를 찾는다. 하위문제는 다음으로 가장 작은 문제를 제일 먼저 시도한다. 예제에선 첫 번째 문자를 뺀 "bcde"다.

reverse("bcde")는 잘 작동한다고 가정하므로, 첫 번째 문자 a는 뒤에 더해주면 된다.

function reverse(string) {
  return reverse(string.slice(1)) + string[0]
}

기저 조건은 문자열에 문자가 하나일 때이므로 해당 조건을 추가해서 처리한다.

function reverse(string) {
  if(string.length === 1) {
    return string[0]
  }
  
  return reverse(string.slice(1)) + string[0]
}

11.3.4 X 세기

주어진 문자열에서 "x"의 개수를 반환하는 countX 함수를 작성한다. "axbxcxd"를 전달하면 "x"의 개수인 3을 반환한다.

하위 문제는 첫 문자를 뺀 "xbxcxd"다. countX("xbxcxd")는 잘 작동한다고 가정하므로, 첫 문자가 "x"면 1을 더하고, 아니라면 아무 것도 더하지 않으면 된다.

function countX(string) {
  if (string[0] === "x") {
    return 1 + countX(string.slice(1));
  } else {
    return countX(string.slice(1));
  }
}

기저 조건을 추가해서 처리하면 된다. 문자열에 문자가 하나만 있을 때가 기저 조건인데, 이 문자가 "x"일 수도 있고 아닐 수도 있어서 기저 조건이 두 개가 돼버린다.

function countX(string) {
  if (string.length === 1) {
    if (string[0] === "x") {
      return 1;
    } else {
      return 0;
    }
  }

  if (string[0] === "x") {
    return 1 + countX(string.slice(1));
  } else {
    return countX(string.slice(1));
  }
}

이를 단순화하는 방법으로 string.slice(1, 1)은 빈 문자열을 반환한다는 것을 이용한다.

function countX(string) {
  if (string.length === 0) return 0;

  if (string[0] === "x") {
    return 1 + countX(string.slice(1, string.length));
  } else {
    return countX(string.slice(1, string.length));
  }
}

이 때 기저 조건은 빈 문자열일 때이다.

문자열에 문자가 하나만 있다면 countX(string.slice(1, 1))를 호출하는데 이것은 countX("")를 호출하는 것이고 이는 기저 조건이므로 0을 반환한다.

11.4 계단 문제

간단한 계산에는 재귀가 필요 없을 수도 있지만, 복잡한 함수라면 재귀적인 사고 방식으로 쉽게 코드를 작성할 수 있다.

계단 문제를 살펴보자. N개 짜리 계단이 있고, 한 번에 1계단에서 3계단까지 올라갈 수 있다. 계단 끝까지 올라가는 경로는 몇 개일까?

11계단이 있을 때, 상향식으로 이 문제를 푸는 것은 쉽지 않다. 하향식으로 생각해야 문제가 단순해진다.

11계단을 오르는 경로의 하위 문제는 10계단을 오르는 경로다. 11계단에 오르려면 적어도 10계단까지 오르는 경로 수 만큼은 필요하다. 10번째 계단까지 오르는 모든 경로에서 한 계단만 더 오르면 되기 때문이다.

하지만 9번째나 8번째 계단에서도 11번째 계단으로 오를 수 있다. 그리고 8번째 계단이나 9번째 계단에서 바로 11번째 계단에 오를 경우 10번째 계단에서 오르는 경로를 따르지 않는다. 10번째 계단을 거치지 않는 경로이기 때문이다.

따라서 꼭대기까지 가는 경로 수는 10번째, 9번째, 8번째 계단까지 가는 모든 경로 수의 합이다. 그 외엔 없다. 7번째 계단에서는 바로 11번째 계단으로 갈 수 없기에 10, 9, 8번째 계단으로 가는 경로를 통해서만 갈 수 있다.

따라서 N개 짜리 계단일 때 경로수는 다음과 같다.

function numberOfPaths(n) {
  return numberOfPaths(n - 1) + numberOfPaths(n - 2) + numberOfPaths(n - 3);
}

간단해 보이지만 이것이 전부 다이고, 기저 조건만 처리하면 된다.

11.4.1 계단 문제 기저 조건

numberOfPath(n) 에서의 기저 조건은 n은 3, 2, 1일 때이다. 이 때 numberOfPath(0), numberOfPath(-1) 등이 호출된다.

이를 해결하기 위해 기저 조건을 전부 하드 코딩할 수 있다.

function numberOfPaths(n) {
  if (n <= 0) return 0;
  if (n === 1) return 1;
  if (n === 2) return 3;
  if (n === 3) return 4;

  return numberOfPaths(n - 1) + numberOfPaths(n - 2) + numberOfPaths(n - 3);
}

효과적인 기저 조건을 다르게 고안해 시스템을 조작할 수도 있다.

function numberOfPaths(n) {
  if (n < 0) return 0;
  if (n === 1 || n === 0) return 1;

  return numberOfPaths(n - 1) + numberOfPaths(n - 2) + numberOfPaths(n - 3);
}

numberOfPaths(1)은 1을 반환해야 하므로 if (n === 1) return 1로 시작한다.

numberOfPaths(2)는 numberOfPaths(1) + numberOfPaths(0) + numberOfPaths(-1)이고, 2여야 한다.

numberOfPaths(1)는 1이므로, numberOfPaths(0)가 1을, numberOfPaths(-1)가 0을 반환하면 numberOfPaths(2)는 2를 반환한다.

따라서 기저조건을 수정한다.

if (n < 0) return 0;
if (n === 1 || n === 0) return 1;

numberOfPaths(3)을 해보면, numberOfPaths(2) + numberOfPaths(1) + numberOfPaths(0)이고 4여야 하는데, 2 + 1 + 1이므로 4를 반환하므로 의도한 값이다.

11.5 애너그램 생성

애너그램은 문자열 내 모든 문자들을 재배열한 문자열이다. "abc"의 애너그램은 ["abc", "acb", "bac", "bca", "cab", "cba"]다.

"abc"의 모든 애너그램을 생성하는 anagram함수가 있을 때 "abcd"의 모든 애너그램을 어떻게 만들 수 있는가?

한 가지 방법으로 "abc"의 애너그램 6개에 대해 각 애너그램 내 가능한 자리마다 "d"를 붙여 만들 수 있다.

function anagramsOf(string) {
  // 기저 조건: 인자 문자열이 한 글자일 때
  // 문자 하나짜리 문자열만 포함하는 배열을 반환한다.
  if (string.length === 1) return [string[0]];

  // 애너그램을 저장할 배열을 만든다
  const collection = [];

  // 두 번째 문자부터 마지막 문자까지의 부분 문자열에서 모든 애너그램을 찾는다.
  const substringAnagrams = anagramsOf(string.slice(1));

  // 모든 애너그램을 순회한다
  for (let i = 0; i < substringAnagrams.length; i++) {
    // 각 애너그램의 인덱스를 순회한다.
    for (let j = 0; j <= substringAnagrams[i].length; j++) {
      const copy = new String(substringAnagrams[i]);
      // 각 인덱스를 순회하며 string의 첫 문자를 삽입한다.
      // 삽입한 후 애너그램 컬렉션에 추가한다.
      collection.push(
        copy.slice(0, j) + string[0] + copy.slice(j, copy.length)
      );
    }
  }

  return collection;
}

재귀를 쓴다고 코드에서 반복문을 전부 없애야 한다는 뜻은 아니다. 문제를 가장 자연스럽게 해결할 수 있는 방식을 선택하면 된다.

11.5.1 애너그램 생성의 효율성

애너그램 생성 알고리즘에 3글자의 문자열을 입력하면, 각 문자마다 반복문을 시작한다. 선택한 문자를 맨 앞에 두고, 남은 두 글자 중 하나는 중간에, 다른 하나는 마지막에 위치한다.

"abc"라면, "a"를 맨 앞으로 "b"가 가운데, "c"가 마지막에 올 수도 있고, "c"가 가운데, "b"가 마지막에 올 수도 있다. "a"를 맨앞으로 하는 애너그램은 총 두 가지이다.

따라서, 3글자의 문자열이라면 애너그램이 3 * 2 * 1 = 6개이다. 4글자의 문자열이라면 4 * 3 * 2 * 1 = 24개이다. 문자열 길이 N에 대해 N!개의 애너그램이 반환된다.

즉, 애너그램 생성 알고리즘은 O(N!)이다. 이를 계승 시간이라고도 부른다.

O(N!)은 매우 느리지만 모든 애너그램을 생성해야 하는 알고리즘에는 더 나은 방법이 없다.

11.6 마무리

재귀는 다양한 문제를 해결하는 훌륭한 도구이지만 주의 깊게 사용하지 않으면 코드가 현저히 느려진다.