이제 관건은 모든 단어를 만들어 내는 것입니다. 단어들은 재귀를 이용하여 어떻게 생성할 수 있을지 살펴봅시다.

재귀 정의

단어를 생성하려면 A, E, I, O, U를 하나씩 이어 붙여 가야 합니다. 즉, 단어에 5개의 문자를 하나씩 이어 주어야 합니다.

▲ 그림 5-7 단어가 만들어지는 과정

따라서 상태는 현재까지 이어 붙인 단어가 되고, (word)로 표기할 수 있습니다. 그리고 이 상태는 word로 시작하는 모든 단어를 반환합니다.

이처럼 단어 자체가 상태가 되기 때문에 종료 조건과 점화식도 쉽게 파악할 수 있습니다. 종료 조건은 단어 길이가 5에 도달했을 때가 됩니다. 이때는 더 이상 뒤에 문자를 이어 붙일 수 없으므로 word만 반환됩니다. 마지막으로 점화식은 word에 A, E, I, O, U를 이어 붙이는 것이 됩니다.