재귀 알고리즘

2.1 파일 트리 순회

파일 트리를 순회하는 재귀 알고리즘을 알아보자. 이 알고리즘은 디렉토리와 모든 하위 디렉토리를 순회하며 모든 파일과 폴더의 목록을 출력한다.

import os

def list_files_recursive(directory, indent=0):
    # 현재 디렉토리에서 모든 파일과 폴더를 가져옵니다
    items = os.listdir(directory)
                
    for item in items:
        # 파일이나 폴더의 전체 경로를 만듭니다
        path = os.path.join(directory, item)
                    
        # 구조를 더 잘 이해할 수 있도록 들여쓰기를 추가하여 출력합니다
        print(' ' * indent + item)
                    
        # 폴더라면, 내용을 재귀적으로 순회합니다
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# 사용 예
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

어떻게 작동하나요?

1. 함수 list_files_recursive(directory, indent=0):
   • directory — 우리가 출력하고자 하는 현재 디렉토리.
   • indent — 파일과 폴더의 중첩을 보여주는 현재 들여쓰기 수준.
2. 현재 디렉토리에서 모든 파일과 폴더 목록을 가져온다 os.listdir(directory)를 사용하여.
3. 각 항목을 순회한다 목록 items에서.
4. 항목의 전체 경로를 만든다 os.path.join(directory, item)를 사용하여.
5. 항목의 이름을 출력한다 각 중첩 수준마다 4칸의 공백을 더하여.
6. 항목이 폴더인지 확인한다 os.path.isdir(path)를 사용하여. 만약 그렇다면, 재귀적으로 list_files_recursive(path, indent + 4)를 호출하여 내용을 순회한다.

출력 예:

다음과 같은 디렉토리 구조가 있다고 가정하자:

root_directory/
    file1.txt
    dir1/
        file2.txt
        file3.txt
        dir2/
            file4.txt
    file5.txt

함수 list_files_recursive(root_directory)를 실행하면 다음과 같은 출력이 나온다:

file1.txt
dir1
    file2.txt
    file3.txt
    dir2
        file4.txt
file5.txt

이 알고리즘은 디렉토리 트리를 재귀적으로 순회하며 모든 파일과 폴더를 중첩을 고려하여 출력한다.

2.2 하노이의 탑

"하노이의 탑" 문제

하노이의 탑은 보조 막대를 사용하여 하나의 막대에서 다른 막대로 원반을 옮기는 고전적인 재귀 문제다.

규칙:

1. 한 번에 하나의 원반만 이동할 수 있다.
2. 원반은 빈 막대나 더 큰 원반 위에만 놓을 수 있다.
3. 모든 원반을 보조 막대를 사용하여 하나의 막대에서 다른 막대로 옮겨야 한다.

이 문제를 해결하는 재귀 알고리즘:

하노이의 탑 알고리즘은 다음과 같이 문제를 해결한다:

1. n - 1 개의 원반을 시작 막대에서 보조 막대로 목적지를 사용하여 옮긴다.
2. 남은 원반을 시작 막대에서 목적지로 옮긴다.
3. n - 1 개의 원반을 보조 막대에서 목적지로 시작 막대를 사용하여 옮긴다.

Python 예제

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"하나의 원반을 {source}에서 {target}로 이동")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"원반 {n}을 {source}에서 {target}로 이동")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# 사용 예:
n = 3  # 원반의 수
hanoi_tower(n, 'A', 'C', 'B')
        

어떻게 작동하나요?

기본 사례:

원반이 하나일 경우 (n == 1), 그냥 시작 막대에서 목적지로 옮긴다.

if n == 1:
    print(f"하나의 원반을 {source}에서 {target}로 이동")
    return

재귀 사례:

1단계. n-1개의 원반을 시작 막대에서 보조 막대로 목적지를 사용하여 이동.

hanoi_tower(n - 1, source, auxiliary, target)

2단계. 원반 n을 시작 막대에서 목적지로 이동.

print(f"원반 {n}을 {source}에서 {target}로 이동")

3단계. n - 1개의 원반을 보조 막대에서 목적지로 시작 막대를 사용하여 이동.

hanoi_tower(n - 1, auxiliary, target, source)

출력 예:

세 개의 원반 (n = 3)이 A, B, C 막대에 있는 경우, 프로그램은 다음을 출력한다:

하나의 원반을 A에서 C로 이동
원반 2을 A에서 B로 이동
하나의 원반을 C에서 B로 이동
원반 3을 A에서 C로 이동
하나의 원반을 B에서 A로 이동
원반 2을 B에서 C로 이동
하나의 원반을 A에서 C로 이동

2.3 코흐의 눈송이

재귀를 사용하여 눈송이를 그리는 것은 프랙탈을 공부하는 데 자주 사용되는 흥미로운 문제이다. 눈송이를 그리는 간단한 방법 중 하나는 프랙탈 곡선을 나타내는 코흐의 곡선을 사용하는 것이다.

코흐의 눈송이를 그리는 알고리즘

코흐의 곡선은 다음과 같이 구성된다:

• 직선으로 시작한다.
• 각 선분을 세 부분으로 나누고 중앙 부분을 작은 "모서리" 곡선으로 대체한다.
• 이 과정을 각 선분에 대해 재귀적으로 반복한다.

단계별 설명

• 시작: 초기 선분을 그린다.
• 분할: 각 선분을 세 부분으로 나눈다.
• 중앙 부분 교체: 두 개의 선으로 60도 각도를 이루는 "모서리"를 중앙 부분에 그린다.
• 과정을 반복: 각 선분에 대해 이 과정을 계속한다.

Turtle 라이브러리를 사용한 Python 예제

import turtle

def draw_koch_curve(t, length, depth):
    if depth == 0:
        t.forward(length)
    else:
        length /= 3.0
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
        t.right(120)
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
            
def draw_snowflake(t, length, depth):
    for _ in range(3):
        draw_koch_curve(t, length, depth)
        t.right(120)
            
# 화면 설정
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# 거북이 설정
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# 눈송이 그리기
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# 그리기 완료
turtle.done()
            

어떻게 작동하나요?

1. 함수 draw_koch_curve(t, length, depth):

• t: 그림을 그리는 거북이.
• length: 선분의 길이.
• depth: 세부 수준을 결정하는 재귀 깊이.

2. 기본 사례:

만약 depth가 0이라면, 거북이는 직선을 그린다.

if depth == 0:
    t.forward(length)
        

3. 재귀 사례:

선분을 세 부분으로 나누고 draw_koch_curve를 각 부분에 재귀적으로 적용하여 회전을 추가한다.

length /= 3.0
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)
t.right(120)
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)

4. 함수 draw_snowflake(t, length, depth):

세 개의 코흐 곡선을 그려 하나의 눈송이로 연결한다.

for _ in range(3):
    draw_koch_curve(t, length, depth)
    t.right(120)

코드 실행 방법

• Turtle 라이브러리가 설치되어 있는지 확인하세요 (pip install PythonTurtle).
• 코드를 .py 파일에 복사하여 붙여넣고 실행하세요. 화면에서 눈송이가 그려지는 모습을 볼 수 있습니다.

이 알고리즘은 간단한 재귀와 기하학적 구성을 사용하여 눈송이의 프랙탈 구조를 시각화할 수 있게 한다.