이제까지 살펴본 재귀의 예에서는 계산할 때마다 재귀 호출을 한 번 해야 했습니다. 그렇지만 때때로 여러 번 재귀 호출을 해야 할 때도 있습니다. 아래는 시어핀스키 가스켓(Sierpinski Gasket)이라고 알려진 프랙탈 구조입니다.
위에서 볼 수 있듯이 어떤 정사각형 영역에 특정한 패턴으로 조그만 정사각형들을 계속 그려 넣은 것입니다. 이를 그리는 방법은 다음과 같습니다. 큰 정사각형 영역에서 시작해서 이를 다음과 같이 네 영역으로 나눕니다.
3개 영역—왼쪽 위, 오른쪽 위, 오른쪽 아래—에 ×를 그린 후 이들을 다시 4개 영역으로 나눕니다.
계속해서 그립니다. × 가 표시된 모든 정사각형을 네 개 영역을 나누고 왼쪽 위, 오른쪽 위, 오른쪽 아래 영역에 × 를 그리고 왼쪽 아래는 항상 그대로 둡니다.
정사각형이 충분히 작아지면 나누는 것을 중지합니다. × 가 있는 모든 정사각형을 채워 넣고 그 외 정사각형을 그대로 두면 이제 시어핀스키 가스켓 패턴이 생깁니다. 다시 한 번 봅시다:
요약하자면, 정사각형에 시어핀스키 가스켓을 그리는 방법은 다음과 같습니다.
  • 정사각형을 얼마나 작게 할지 결정합니다. 탈출 조건에 해당할 만큼 작다면 정사각형을 채웁니다. 얼마나 작은 것이 탈출 조건에 해당하는지는 정할 수 있습니다.
  • 탈출 조건에 해당할 만큼 작지 않다면, 정사각형을 왼쪽 위, 오른쪽 위, 오른쪽 아래, 왼쪽 아래로 나누어 줍니다. 그리고 다음 하위 문제 세 개를 해결합니다:
    1. 왼쪽 위 정사각형에 시어핀스키 가스켓을 그립니다.
    2. 오른쪽 위 정사각형에 시어핀스키 가스켓을 그립니다.
    3. 오른쪽 아래 정사각형에 시어핀스키 가스켓을 그립니다.
재귀 호출을 한 번이 아닌 세 번해야 합니다. 여러 번 재귀 호출을 하는 예로 시어핀스키 가스켓을 사용하는 이유입니다.
재귀로 시어핀스키 가스켓을 그리는 네 개중 세 개의 정사각형은 아무렇게나 고를 수 있습니다. 고른 것에 따라 결과는 위의 그림에서 90도 단위로 회전합니다. (시어핀스키 가스켓을 그리는 정사각형 수를 다르게 바꾼다면 흥미로운 결과가 나오지 않습니다)
다음 프로그램은 시어핀스키 가스켓을 그리는 프로그램입니다. 주석을 달거나 해제하여 시어핀스키 가스켓을 회전시켜 보세요:

위 자료는 다트머스 대학교 컴퓨터공학과토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.
로딩 중