이 실험 소개
나무는 줄기 위에 더 작은 나무 두 그루가 있는 모양입니다. 이 한 문장만으로 완전한 프로그램이 됩니다. 가지를 그린 다음 자기 자신을 두 번 호출하는 함수죠. 재귀는 짧은 규칙으로 풍부한 그림을 만들어 냅니다. 나무와 시에르핀스키 삼각형, 코흐 눈송이가 호출을 거듭하며 만들어지는 모습을 보고, 호출 스택이 늘고 줄어드는 과정을 따라가며 깊이가 커질수록 호출 횟수가 얼마나 빠르게 폭증하는지 세어 보세요.
학습 목표
- 재귀 함수의 기본 사례와 재귀 사례를 구분하기
- 재귀 호출이 실행되고 반환되는 순서를 추적하기
- 호출 스택에 무엇이 저장되는지, 그리고 스택의 깊이가 중요한 이유를 설명하세요
- 이진 트리의 2^(n+1) − 1과 같이 주어진 깊이에 대한 호출 횟수를 계산하세요
- 자기 유사성을 설명하고 간단한 프랙털 차원을 계산하세요
사용 방법
- 1깊이 3인 트리를 선택하고 호출 과정을 천천히 살펴보세요. 왼쪽 가지와 오른쪽 가지 중 어느 쪽이 먼저 그려지나요? 왜 그런가요?
- 2스택이 가장 깊어진 지점에서 일시 정지하세요. 스택의 각 프레임은 무엇을 나타내나요? 깊이와 비교하면 프레임은 몇 개 있나요?
- 3트리의 깊이와 호출 횟수 표를 완성하세요. 규칙을 찾아 깊이 10에서 확인하세요.
- 4가지의 각도와 길이 비율을 바꿔 보세요. 어떤 설정에서 가지가 서로 겹치나요?
- 5시에르핀스키 삼각형으로 전환하세요. 코드에서 기본 사례는 어디에 있나요? 깊이 5에서 삼각형은 몇 개 그려지나요?
- 6깊이 5의 코흐 눈송이를 만드세요. 표시된 값을 사용해 둘레는 계속 늘어나면서도 넓이는 유한하게 유지될 수 있는 이유를 설명하세요.
모델
가정
- 호출은 일반적인 프로그래밍 언어에서 실행되는 것과 정확히 같은 방식으로, 프로그램 순서에 따라 깊이 우선으로 하나씩 실행됩니다.
- 의사 코드는 위치와 방향을 매개변수로 전달하므로, 호출이 반환된 후 터틀의 상태를 복원할 필요가 없습니다.
- 나무의 프랙탈 차원 log 2 / log(1/r)은 가지가 서로 겹치지 않을 때만 가지 끝을 설명합니다.
- 단계별 재생이 빠르게 유지되도록 최대 깊이를 제한합니다. 나무는 12, 삼각형은 7, 눈송이는 6입니다.
수업에서 해 보기
- Q1나무 함수에 기저 사례가 없다면 어떤 일이 일어날까요?
- Q2깊이가 4일 때 시어핀스키 함수는 몇 번 호출되나요? 합을 사용해 답을 설명하세요.
- Q3수천 번 호출되는데도 호출 스택의 깊이가 재귀 깊이에 1을 더한 값보다 커지지 않는 이유는 무엇인가요?
- Q4n!을 계산하는 재귀 함수를 작성하고 기저 사례를 밝히세요.
- Q5측정에 사용하는 자가 짧을수록 영국의 해안선은 더 길어 보입니다. 코흐 눈송이는 이를 어떻게 설명할까요?
자주 묻는 질문
재귀는 반복문보다 느린가요?
호출할 때마다 스택 프레임에 약간의 시간과 메모리가 들기 때문에 반복문이 대체로 조금 더 빠릅니다. 하지만 트리, 중첩 폴더, 구문 분석 같은 분기 구조에서는 재귀가 훨씬 간단하게 작성할 수 있습니다. 또한 어떤 재귀든 직접 명시적인 스택을 사용하는 방식으로 다시 작성할 수 있습니다.
스택 오버플로란 무엇인가요?
끝나지 않은 호출은 각각 호출 스택에 프레임을 유지합니다. 재귀가 너무 깊어지면, 예를 들어 기저 사례에 도달하지 못하면 스택 메모리가 고갈되고 프로그램은 스택 오버플로 오류와 함께 충돌합니다.
자연에서 프랙탈은 어디에서 볼 수 있나요?
양치식물, 로마네스코 브로콜리, 하천망, 번개, 혈관, 폐의 분기된 기도는 모두 여러 규모에 걸쳐 대략적인 자기 유사성을 보입니다. 그래서 컴퓨터 그래픽에서는 이를 생성하는 데 재귀 규칙을 사용합니다.