1.1.3 순열을 재귀 함수로 구현하기: 재귀 트리 사용하기

재귀 함수를 사용하는 두 번째 예로, 어떤 집합이 주어졌을 때 그 집합의 모든 순열을 구하는 프로그램을 만들어 보겠습니다. 순열(permutation)이란 순서가 있는 집합을 다른 순서로 섞는 것입니다. 예를 들어 집합 S={1, 2, 3}이 주어질 때 순서를 섞어 얻은 {2, 1, 3}은 집합 S의 한 순열입니다. 그럼 집합 S의 모든 순열을 나열해 볼까요?

{1, 2, 3}

{1, 3, 2}

{2, 1, 3}

{2, 3, 1}

{3, 1, 2}

{3, 2, 1}

우리가 모든 순열을 구했는지 어떻게 알 수 있을까요? 집합 원소 개수가 n일 때 모든 순열 개수는 n!입니다. 예를 들어 집합 S는 원소 개수가 3입니다. 첫 번째 위치에 올 수 있는 가능성을 가진 원소는 1, 2, 3 세 개입니다. 첫 번째 원소를 고르고 나서 그다음으로 고를 수 있는 원소는 두 개가 될 것이고, 마지막으로 고를 수 있는 원소는 한 개이겠지요. 즉, 3×2×1이므로 3!이 됩니다.

재귀 함수를 구현할 때 두 가지가 중요하다고 앞서 설명했습니다. 바로 기저 사례와 매개변수의 설계입니다. 이를 위해서는 먼저 문제를 정의해야만 합니다. 이 절에서 해결하려고 하는 문제는 개수가 n인 집합의 모든 순열입니다. 이 문제를 형태는 비슷하지만 크기가 다른 여러 작은 문제들로 나누어 보겠습니다. 일단 작은 크기의 문제로 나눈 후 답을 구하고 그 답을 합치면 될 것입니다.