permutation() 함수가 순열을 출력하는 프로그램이라고 하면 다음과 같이 표현할 수 있습니다.

문제: permutation({1, 2, 3})

- 부분 문제 1: 1을 출력 후 permutation({2, 3})

- 부분 문제 2: 2를 출력 후 permutation({1, 3})

- 부분 문제 3: 3을 출력 후 permutation({1, 2})

이 표현은 문제(problem)를 여러 개의 부분 문제(subproblem)로 쪼갠 후 그 해답을 구하는 과정입니다. 이를 그림으로 나타내 보겠습니다(그림 1-3). 그러면 다음 형태가 되는데, 이를 재귀 트리(recursive tree)라고 합니다.

▲ 그림 1-3 재귀 트리

그림 1-3의 재귀 트리에서 각 사각형은 스택 프레임을 의미합니다. 사각형 내부의 {}는 함수에 전달할 매개변수를 나타냅니다. {} 안에 있는 원소 개수가 부분 문제 크기인데 아래로 내려갈수록 집합 개수가 적어지고 있지요. 이렇게 계속 집합 크기가 작아지면 결국 공집합에 도달하게 될 것입니다. 그때가 바로 기저 사례가 되겠군요.