재귀 (Recursion)#
재귀는 컴퓨터 과학과 수학에서 매우 중요한 문제 해결 기법으로, 자기 자신을 호출하는 함수나 알고리즘을 통해 복잡한 문제를 더 작고 동일한 형태의 하위 문제로 나누어 해결하는 방법이다.
재귀는 복잡한 문제를 더 작고 관리하기 쉬운 부분으로 나누는 강력한 문제 해결 기법이다.
재귀적 접근법은 많은 컴퓨터 과학 알고리즘과 자료구조의 기반이 된다.
효과적인 재귀 알고리즘을 작성하려면 기저 조건을 명확히 정의하고, 문제를 적절히 분해하며, 필요한 경우 최적화 기법을 사용해야 한다.
재귀에 익숙해지면 이전에는 복잡하게만 보였던 많은 문제를 우아하고 효율적으로 해결할 수 있습니다.
재귀의 기본 개념#
재귀는 문제를 자기 자신과 동일하지만 더 작은 규모의 문제로 분해하여 해결하는 접근법이다.
이러한 접근법은 다음과 같은 두 가지 핵심 요소로 구성된다:
- 기저 조건(Base Case): 재귀 호출이 종료되는 조건으로, 더 이상 자기 자신을 호출하지 않고 직접 답을 반환한다.
- 재귀 단계(Recursive Step): 문제를 더 작은 하위 문제로 나누고 자기 자신을 호출하여 해결하는 단계이다.
재귀의 작동 원리#
재귀 함수가 호출될 때마다 새로운 함수 호출 스택 프레임이 생성되며, 이 프레임에는 해당 함수 호출의 매개변수와 지역 변수가 저장된다. 함수가 종료되면 해당 스택 프레임이 제거되고 이전 함수 호출로 돌아간다.
재귀 예제: 팩토리얼 계산#
팩토리얼은 재귀의 고전적인 예.
n!은 n부터 1까지의 모든 정수의 곱.
1
2
3
4
5
6
7
8
9
10
11
| def factorial(n):
# 기저 조건: n이 0 또는 1이면 1을 반환
if n <= 1:
return 1
# 재귀 단계: n * (n-1)!
else:
return n * factorial(n-1)
# 팩토리얼 실행 예시
result = factorial(5) # 5! = 5 * 4 * 3 * 2 * 1 = 120
print(result) # 출력: 120
|
이 예제에서 n <= 1은 기저 조건이고, n * factorial(n-1)은 재귀 단계입니다.
실행과정
1
2
3
4
5
| factorial(5) → 5 * factorial(4)
→ 4 * factorial(3)
→ 3 * factorial(2)
→ 2 * factorial(1)
→ 1
|
이 함수는 n이 0일 때 1을 반환하는 기본 조건과, n과 factorial(n-1)을 곱하는 재귀 호출로 구성되어 있다.
재귀적 사고방식#
재귀적으로 생각하는 것은 처음에는 어려울 수 있지만, 다음과 같은 접근 방식이 도움이 된다:
- 문제 분해: 주어진 문제를 동일한 형태의 더 작은 하위 문제로 나눈다.
- 기저 조건 식별: 더 이상 분해할 수 없는 가장 작은 문제(기저 조건)를 식별한다.
- 재귀 관계 정의: 원래 문제와 하위 문제 사이의 관계를 정의한다.
재귀의 장단점#
- 코드가 간결하고 이해하기 쉬워진다.
- 문제의 자연스러운 구조를 따른다.
- 복잡한 문제를 더 작고 관리하기 쉬운 부분으로 나눌 수 있다.
- 함수 호출마다 스택 프레임이 생성되어 메모리 사용량이 증가한다.
- 깊은 재귀 호출은 스택 오버플로우를 일으킬 수 있다.
- 동일한 하위 문제가 여러 번 계산될 수 있어 비효율적일 수 있다(이는 메모이제이션으로 해결 가능).
고급 재귀 기법#
꼬리 재귀(Tail Recursion)
꼬리 재귀는 재귀 호출이 함수의 마지막 연산인 경우이다.
이는 컴파일러가 최적화하여 스택 사용을 줄일 수 있다.
1
2
3
4
5
| def factorial_tail(n, accumulator=1):
if n <= 1:
return accumulator
else:
return factorial_tail(n-1, n * accumulator)
|
메모이제이션(Memoization)
메모이제이션은 이미 계산한 결과를 저장하여 동일한 계산을 여러 번 수행하지 않도록 하는 기법.
1
2
3
4
5
6
7
| def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
|
실제 응용 사례#
재귀는 다음과 같은 다양한 문제 해결에 활용된다:
- 트리와 그래프 탐색: 깊이 우선 탐색(DFS)은 본질적으로 재귀적이다.
- 분할 정복 알고리즘: 퀵 정렬, 병합 정렬과 같은 정렬 알고리즘은 재귀를 사용한다.
- 동적 프로그래밍: 많은 동적 프로그래밍 문제는 재귀로 표현할 수 있다.
- 백트래킹: 스도쿠 해결, N-퀸 문제와 같은 백트래킹 알고리즘은 재귀를 사용한다.
재귀 예제: 하노이 탑#
하노이 탑은 재귀의 고전적인 예제.
세 개의 기둥과 크기가 다른 n개의 원판이 있으며, 목표는 모든 원판을 첫 번째 기둥에서 세 번째 기둥으로 옮기는 것.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| def hanoi_tower(n, source, auxiliary, target):
# 기저 조건: 원판이 1개만 있으면 직접 옮깁니다
if n == 1:
print(f"원판 1을 {source}에서 {target}으로 이동")
return
# 재귀 단계 1: n-1개의 원판을 source에서 auxiliary로 이동
hanoi_tower(n-1, source, target, auxiliary)
# 가장 큰 원판을 source에서 target으로 이동
print(f"원판 {n}을 {source}에서 {target}으로 이동")
# 재귀 단계 2: n-1개의 원판을 auxiliary에서 target으로 이동
hanoi_tower(n-1, auxiliary, source, target)
# 실행 예시: 3개의 원판을 A에서 C로 이동
hanoi_tower(3, 'A', 'B', 'C')
|
재귀와 반복의 비교#
모든 재귀 알고리즘은 반복(loop)으로 변환할 수 있다.
재귀 대신 반복을 사용하면 메모리 사용을 줄일 수 있지만, 코드가 더 복잡해질 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
| # 재귀 방식의 팩토리얼
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n-1)
# 반복 방식의 팩토리얼
def factorial_iterative(n):
result = 1
for i in range(1, n+1):
result *= i
return result
|
재귀적 자료구조#
재귀는 자료구조에도 적용된다.
연결 리스트, 트리, 그래프와 같은 자료구조는 재귀적으로 정의되며, 이러한 자료구조를 처리하는 알고리즘도 종종 재귀적.
예를 들어, 이진 트리의 순회:
1
2
3
4
5
6
7
8
9
10
11
12
| class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def inorder_traversal(root):
if root is None:
return []
# 왼쪽 하위 트리 -> 루트 -> 오른쪽 하위 트리 순으로 순회
return inorder_traversal(root.left) + [root.value] + inorder_traversal(root.right)
|
재귀의 응용#
재귀는 다양한 알고리즘과 자료구조에서 활용된다:
- 정렬 알고리즘: 퀵 정렬, 병합 정렬
- 탐색 알고리즘: 깊이 우선 탐색(DFS)
- 동적 프로그래밍: 피보나치 수열 계산
- 수학적 문제: 하노이의 탑, 조합 계산
실제 예시#
- HTML DOM 순회
1
2
3
4
5
6
7
| def traverse_dom(element):
# 현재 요소 처리
print(element.tag_name)
# 모든 자식 요소에 대해 재귀 호출
for child in element.children:
traverse_dom(child)
|
- 폴더 내 파일 찾기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| import os
def find_files(folder_path, extension):
files = []
# 현재 폴더의 내용물 확인
for item in os.listdir(folder_path):
full_path = os.path.join(folder_path, item)
if os.path.isfile(full_path): # 파일인 경우
if item.endswith(extension):
files.append(full_path)
else: # 폴더인 경우
# 재귀적으로 하위 폴더 검색
files.extend(find_files(full_path, extension))
return files
# 사용 예
pdf_files = find_files("C:/Documents", ".pdf")
|
- 디렉토리 크기 계산
1
2
3
4
5
6
7
8
9
10
11
12
13
| def get_folder_size(folder_path):
total_size = 0
for item in os.listdir(folder_path):
item_path = os.path.join(folder_path, item)
if os.path.isfile(item_path):
total_size += os.path.getsize(item_path)
else:
# 폴더인 경우 재귀적으로 크기 계산
total_size += get_folder_size(item_path)
return total_size
|
참고 및 출처#
Recursion vs. Iteration Iteration과 Recursion은 프로그래밍에서 반복적인 작업을 수행하는 두 가지 주요 방식이다.
Iteration은 루프를 사용하여 특정 조건이 만족될 때까지 코드 블록을 반복 실행하는 방식이다.
주로 for, while 등의 루프 구조를 사용한다.
Iteration은 명시적인 반복 구조를 가지며, 각 반복마다 변수의 상태가 변경된다.
Recursion은 함수가 자기 자신을 호출하여 문제를 해결하는 방식이다.
복잡한 문제를 더 작고 간단한 문제로 나누어 해결한다.
Recursion은 base case(종료 조건)와 recursive case(재귀 호출)로 구성된다.
Iteration vs. Recursion 특성 Iteration Recursion 정의 루프를 사용한 반복 실행 함수가 자기 자신을 호출 제어 구조 루프 (for, while 등) 함수 호출 스택 종료 조건 루프 조건이 거짓이 될 때 Base case에 도달할 때 메모리 사용 일반적으로 적음 함수 호출 스택으로 인해 많음 속도 대체로 빠름 대체로 느림 (오버헤드 존재) 코드 복잡성 간단한 문제에 적합 복잡한 문제 해결에 유용 무한 반복 위험 루프 조건 오류 시 발생 Base case 누락 시 발생 문제 해결 접근 순차적 실행 분할 정복 가독성 단순한 경우 높음 복잡한 경우 높음 디버깅 상대적으로 쉬움 상대적으로 어려움 두 방식 모두 장단점이 있으며, 문제의 특성과 요구사항에 따라 적절한 방식을 선택해야 한다.
Iteration은 단순하고 반복적인 작업에 적합하며, Recursion은 복잡한 문제를 분할하여 해결하는 데 유용하다.
...