빈 문자열을 넘겼을 때의 재귀 과정을 그림으로 살펴봅시다.

▲ 그림 5-8 빈 문자열을 넘겼을 때의 재귀 과정

그림 5-8에서 재귀는 화살표를 따라 진행하면서 이 과정에서 생성되는 모든 단어를 저장합니다. 무언가 눈치챘나요? 재귀를 진행하면서 생성되는 단어들은 이미 사전 순으로 정렬되어 있습니다. 이는 재귀의 특성인데, 재귀는 하나의 상태가 여러 상태로 전이될 때 종료 조건에 도달할 때까지 첫 번째 전이를 계속합니다.

이 경우 A, E, I, O, U를 이용하여 5개의 상태로 전이되는데, 첫 번째 전이인 A를 붙이는 전이가 종료 조건에 도달할 때까지 계속되는 것입니다. 따라서 A만으로 구성된 단어들이 가장 먼저 생성되고, 가장 마지막 재귀부터 다음 전이를 선택합니다.