8. 재귀 & 백트래킹

8. 재귀 & 백트래킹

1. 재귀 (Recursion) 란?

• 함수가 자기 자신을 호출하는 것
• 수학적으로 반복되는 구조를 표현할 때 유용

예: 팩토리얼

n! = n × (n-1)! 5! = 5 × 4 × 3 × 2 × 1

1.1 재귀의 기본 구조

def 함수():
	if 종료조건: # 반드시 필요!
		return
	함수() # 자기자신을 호출

1.2 예제 1 - 팩토리얼

def factorial(n):
	if n == 0:
		return 1
	return n * factorial(n-1)

print(factorial(5)) # 120

⚠️ 중요한 포인트

• 종료 조건(if n == 0) 없으면 무한 루프로 터진다.
• 콜스택(Stack)에 함수들이 쌓였다가 하나씩 빠지면서 계산된다.

1.3 예제 2 - 피보나치 수열

f(n) = f(n-1) + f(n-2), 단 f(0) = 0, f(1) = 1

def fib(n):
	if n <= 1:
		return n
	return fib(n - 1) + fib(n - 2)

⚠️ 이건 동일한 계산을 반복하기때문에 비효율적

나중에 DP에서 메모이제이션으로 최적화함

---

2. 백트래킹 (Backtracking) 이란?

• 모든 경우의 수를 시도하며 정답을 찾는 알고리즘
• “되면 하고, 안 되면 돌아간다(Backtrack)”
• 대표 예: 완전탐색 + 가지치기

2.1 백트래킹 기본 구조

def backtrack(상태):
	if 정답 조건:
		처리 
		return 
	for 선택 in 가능한지 선택지:
		if 유효한 선택인지 검사:
			선택 적용
			bactrack(다음 상태)
			선택 취소 (원상복구)

2.2 예제 1 - 1부터 N까지 모든 순열 구하기

def bactkrack(path, used):
	if len(path) == N:
		print(path)
		return
	else:
		for i in range(1, N+1):
			if not used[i]:
				used[i] = True
				backtrack(path + [i], used)
				used[i] = False
	return

N = int(input())
used = [False] * (N+1)
bactrack([], used)

입력: 3

                                 [ ]
              ┌───────────────────┬───────────────────┐
            [1]                  [2]                 [3]
       ┌─────┴─────┐       ┌─────┴─────┐       ┌─────┴─────┐
     [1,2]       [1,3]   [2,1]       [2,3]   [3,1]       [3,2]
      |            |       |           |       |           |
   [1,2,3]      [1,3,2] [2,1,3]     [2,3,1] [3,1,2]     [3,2,1]

출력:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

---

3. 재귀 vs 백트래킹

항목	재귀	백트래킹
정의	자기 자신 호출	재귀 + 가지치기
목적	반복 계산	모든 경우 탐색
예시	팩토리얼, 피보나치	순열, N-Queen, 미로 탐색
중요 요소	종료 조건	유효성 검사 + 백트래킹(복구)