재귀함수 ) 멍청한 내 동생도 이해시킨 자바스크립트 재귀함수 구현

작성일 In Views: Disqus:

▪︎ 재귀 함수

재귀 함수란 자기 자신을 호출하는 함수를 말합니다. 종료 조건이 충족될 때까지 반복적으로 자신을 호출하면서 주어진 동작을 수행합니다. 재귀 함수는 순회할 대상의 상태를 변경하면서 각 대상마다 비슷한 동작을 수행해야 할 때 효율적으로 사용할 수 있습니다.

[1, 2, 3, 4, 5, 6] 이라는 배열안의 모든 숫자의 합을 구하는 코드를 작성한다고 해보겠습니다. 이 경우 간단하게 배열을 for문으로 순회하는 것으로 풀이가 가능합니다.

[1, 2, 3, [1, 2, [4, 5], 3], 5, 6] 이러한 형태의 배열은 어떨까요? 3중 for문으로 배열들을 순회하면 가능할 것입니다. 그러나 문제에서 주어지는 입력값이 계속 바뀔 수 있고, 어느정도 중첩될지 예측할 수 없는 상황이라면 기존처럼 코드를 구현하기에는 한계가 있을 것입니다. 이 때 재귀함수를 사용하면 효율적이고 가독성있는 코드 작성이 가능합니다.

▫︎ 재귀 함수의 구성

재귀 함수는 크게 종료 조건과 실행할 동작으로 나누어 구성할 수 있습니다. 실행할 동작에서 주어진 데이터들을 가공하고 동작을 수행하면서 자기 자신을 계속 호출하다가 정해놓은 종료 조건에 다달았을 때 함수를 return하게 하는 것입니다.

1
2
3
4
5
6
7
8
9
10
const recursive = (depth, ...) => {
  if( 종료 조건 ) return;

//-------------------------------

  // depth별 실행할 동작
  recursive(depth+1, ...)
};

recursive(1, ...)

▫︎ 재귀 함수의 depth

재귀 함수를 자바스크립트 코드로 처음 구현할 때, 코드의 동작을 따라가며 이해하는 것이 어렵습니다. 그러나 depth 개념을 적용하여 코드를 구현한다면 원활한 이해가 가능합니다. depth는 재귀 함수가 호출된 깊이, 즉 자신을 몇번째 호출했는지에 대한 데이터입니다.

순열과 조합을 예시로 지금까지의 내용들을 적용하여 재귀함수를 이해해보겠습니다.

▪︎ 카드를 뽑아보자

image.png

▫︎ 순열

순열은 순서를 고려하여 카드들을 뽑는 방법입니다. 카드를 하나씩 뽑되, 뽑은 카드는 제외하고 남은 카드들 중에서 하나씩 뽑는 것을 반복하면 됩니다. 그러다가 원하는 개수의 카드를 뽑았을 때 동작을 멈추면 됩니다. 재귀를 사용하면 효율적인 이유는 카드를 뽑는 동작들이 모두 ‘주어진 배열들을 순회하며 하나를 선택한다’라는 같은 동작을 하기 때문입니다. 각 카드를 뽑는 동작, 몇 번째 카드를 뽑는 상황인지에 따라 depth가 부여됩니다. (첫 번째 카드를 뽑으면 depth 1 …)

image.png

이제 우리는 재귀 함수를 구현하기 위해 세가지만 고려하면 됩니다.

  1. 종료 조건
  2. 시행할 동작
  3. 필요한 데이터

  1. 종료 조건은 우리가 카드를 3개 다 뽑았을 경우입니다. 따라서 3의 depth까지만 함수를 실행하고 재귀를 멈추면 됩니다.

  2. 시행할 동작은 남은 카드들 중 한개를 뽑는 것입니다. 카드 배열들을 for문으로 순회하면서 각 자리에 하나씩 넣어주면 됩니다.

  3. 필요한 데이터는 다음 세가지입니다. depth, 남은 카드들의 정보를 담은 배열, 뽑은 카드들의 배열

위 정보를 바탕으로 처음 소개한 재귀 함수와 동일한 구성으로 코드를 구현해보면 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const cards = [1, 2, 3, 4, 5];

// 순열
const answer = [];
const permutation = (depth, leftCards, arr) => {
  // 종료 조건
  if (depth > 3) {
    answer.push(arr);
    return;
  }

  // depth별 실행할 동작
  for (let i = 0; i < leftCards.length; i++) {
    const cardsArr = leftCards.filter((_, idx) => idx !== i); // 다음에 뽑을 수 있는 카드들의 배열
    permutation(depth + 1, cardsArr, [...arr, leftCards[i]]);
  }
};

permutation(1, cards, []);
console.log(answer);

▫︎ 조합

조합은 순서를 고려하지 않고 카드들을 뽑는 방법입니다. 뽑은 카드를 제외하고 다시 카드를 뽑되, 순서가 달라도 같은 카드들을 뽑으면 안되기 때문에 순회할 때 뽑은 카드 뒤쪽의 카드들만을 대상으로 합니다. 이외에는 순열과 같습니다.

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const cards = [1, 2, 3, 4, 5];

// 조합
const answer = [];
const combination = (depth, leftCards, arr) => {
  // 종료 조건
  if (depth > 3) {
    answer.push(arr);
    return;
  }

  // depth별 실행할 함수
  if (leftCards.length === 0) return;

  for (let i = 0; i < leftCards.length; i++) {
    const cardsArr = leftCards.slice(i + 1); // 다음에 뽑을 수 있는 카드들의 배열
    combination(depth + 1, cardsArr, [...arr, leftCards[i]]);
  }
};

combination(1, cards, []);
console.log(answer);

▪︎ Depth가 유동적이라면?

위에 설명한 depth 데이터는 재귀가 몇번째까지 타고 들어가며 실행되는지를 쉽게 이해하기 위해 추가한 개념입니다. depth 개념으로 순열과 조합을 구현해보면서 재귀의 동작에 대해 기본적인 이해가 생겼다면 depth에 기반한 재귀가 아닌 함수 그 자체가 데이터를 변동하며 스스로를 호출하는 경우를 생각해보겠습니다.

위의 depth를 이용한 재귀 함수의 구현은 모든 상황에서 사용할 수는 없습니다. 예를들어 얼만큼 함수를 다시 호출할지가 정해지지 않은 문제의 경우가 그렇습니다. 위의 예시에서는 ‘5장 중 3장의 카드를 뽑는다’ 였지만, 만약 숫자가 적힌 5장의 카드 중 임의의 수의 카드를 뽑아 손안의 카드와 남은 카드를 비교하는 문제에서는 depth를 기준으로 하여 재귀 함수를 호출할 수 없습니다. 아래 문제를 살펴보겠습니다.

image.png

이 문제에서 필요한 정보는 각 부분집합의 경우들과 그와 매치되는 남은 원소들입니다. 위 카드 예시에 대입해보자면 임의의 개수의 카드를 뽑아 순서에 상관하지 않고 뽑는 경우(조합)와 같습니다. 따라서 depth가 아닌 다른 데이터들을 바탕으로 함수를 구성해야 합니다.

임의의 개수의 원소를 뽑는다는 것은 0개 ~ 모든 원소의 개수까지를 뽑아본다는 것입니다. 따라서 조합을 실행하며 선택된 원소의 이전 원소들은 제외하고 남은 원소들의 수가 0이 될 때 함수를 종료하면 될 것 같습니다. 또한 문제를 푸는데 필요한 정보인 각 부분집합, 즉 뽑은 원소들의 배열과 그에 매칭된 남은 원소들이므로 이 둘을 데이터로하여 재귀 함수를 구성하면 문제를 풀 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const n = 6;
const arr = [1, 3, 5, 6, 7, 10];

let answer = "NO";
let arr1 = [];
let arr2 = [];

const recursive = (leftArr, picks) => {
  if (leftArr.length === 0) return;

  for (let i = 0; i < leftArr.length; i++) {
    const newArr = [...picks, leftArr[i]]; // 전체 배열에서 뽑을 수 있는 (남아있는) 카드들
    recursive(leftArr.slice(i + 1), newArr); // i번째 카드를 뽑았다면 i 이후의 카드들이 남아있게 된다.
    arr1.push(newArr);
    arr2.push(arr.filter((el) => !newArr.includes(el)));
  }
};

recursive(arr, []);

for (let i = 0; i < arr1.length; i++) {
  if (arr1[i].reduce((acc, cur) => acc + cur, 0) === arr2[i].reduce((acc, cur) => acc + cur, 0)) answer = "YES";
}
console.log(answer);