[알고리즘] 재귀(Recursion)
재귀란?
함수가 자신 자신을 다시 호출하는 프로그래밍 기법
보통 문제를 더 작은 문제로 나눠서 해결하거나 같은 코드를 반복해서 사용해야할 때 유용하게 사용된다.
def recursive_func() :
print('재귀 함수 호출')
recursive_func()
recursive_func()
재귀의 기본 구조
재귀함수는 기본 조건(종료 조건, Base Case) 과 재귀 호출(Recursive Case) 로 이루어져있다.
- 기본 조건(Base Case): 재귀 호출을 멈추는 조건 (없으면 무한 호출로 오류 발생!)
- 재귀 호출(Recursive Case): 자기 자신을 호출하면서 문제를 점점 작게 만듦
재귀를 할 때 유의해야할 점은 종료 조건(Break Point)을 꼭 명시해줘야 한다는 점이다.
ex 1. Factorial
팩토리얼은 다음과 같이 정의되는 식이다.
n! = n x (n-1)!
그리고 종료 조건은 0! = 1 이다.
def factorial(n):
if n == 0: # 기본 조건 (종료 조건)
return 1
return n * factorial(n - 1) # 재귀 호출
print(factorial(5)) # 5! = 5 × 4 × 3 × 2 × 1 = 120
ex 2. 피보나치 수열
피보나치 수열은 다음과 같이 정의된다.
F(n) = F(n-1) + F(n-2)
F(0) = 0, F(1) = 1
def fibonacci(n):
if n == 0: # 기본 조건
return 0
elif n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2) # 재귀 호출
print(fibonacci(6)) # 8 (0, 1, 1, 2, 3, 5, 8)그러나 피보나치처럼 같은 값을 여러 번 계산하는 경우 중복 연산이 많아진다.
→ 이는 메모이제이션(Memoization)이나 DP 기법 사용하면 해결 가능!
종료 조건이 없다면 무한루프를 돌까?
재귀를 위 같이 정의하여 자기 자신을 계속 불러오면 이론상으로는 자기 자신을 불러온다. 그러나 실제 실행 하면 RecursionError가 발생한다. 즉, 스택 오버플로우(Stack Overflow)가 발생하는데, 보통 파이썬 인터프리터는 호출 횟수 제한이 있는데 이 한계를 벗어났기 때문에 발생한다. 따라서 무한대로 재귀 호출을 진행할 수는 없다.
그러나 재귀가 마냥 좋은 방법은 아닐 수 있다! 반복 계산이 많아져 경우에 따라 시간복잡도가 더 나빠질 수도 있다.
✅ 재귀가 시간복잡도를 줄이는 경우
재귀가 문제를 작은 부분 문제로 나누고, 중복 연산이 적을 때 시간복잡도가 줄어들 수 있다.
예를 들어, 이진 탐색(Binary Search) 는 재귀를 사용하면 시간복잡도가 O(log N) 으로 줄어들어든다.
📌 이진 탐색 (Binary Search) 예제
정렬된 리스트에서 특정 값을 찾는 문제를 재귀적으로 구현하면:
def binary_search(arr, target, left, right):
if left > right:
return -1 # 탐색 실패
mid = (left + right) // 2 # 중간 인덱스
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, target, left, mid - 1) # 왼쪽 반 탐색
else:
return binary_search(arr, target, mid + 1, right) # 오른쪽 반 탐색
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7, 0, len(arr) - 1)) # 출력: 3 (인덱스)🔹 시간복잡도: O(log N)
🔹 왜 빠를까? 한 번 탐색할 때마다 탐색 범위가 절반으로 줄어들기 때문
❌ 재귀가 시간복잡도를 증가시키는 경우
재귀를 사용할 때, 같은 연산을 여러 번 반복하면 비효율적이다.
피보나치 수열을 단순 재귀로 구현하면 O(2ⁿ) 시간복잡도를 가진다.
📌 피보나치 (비효율적인 재귀)
def fibonacci(n):
if n == 0 or n == 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(6)) # 출력: 8🔺 시간복잡도: O(2ⁿ)
🔺 왜 느릴까? 같은 값을 여러 번 계산하기 때문! (중복 계산)
✅ 재귀 최적화 (DP + 메모이제이션)
위의 피보나치 문제를 메모이제이션 (Memoization) 기법을 사용해 개선하면 O(N)으로 최적화 가능하다
def fibonacci_dp(n, memo={}):
if n in memo:
return memo[n]
if n == 0 or n == 1:
return n
memo[n] = fibonacci_dp(n - 1, memo) + fibonacci_dp(n - 2, memo)
return memo[n]
print(fibonacci_dp(50)) # 빠르게 실행된다!🔹 시간복잡도: O(N)
🔹 왜 빠를까? 중복 계산을 피하기 위해 이미 계산한 값을 저장하고 재사용하기 때문
정리하자면!
✅ 재귀가 항상 시간복잡도를 줄이는 것은 아니다!
✅ 잘 사용하면 O(log N)으로 최적화할 수 있지만, 잘못 사용하면 O(2ⁿ)로 폭발할 수도 있다.
✅ 중복 계산이 많으면 메모이제이션(DP) 또는 반복문으로 최적화하는 것이 중요하다! 🚀
그러면 어느 유형의 코딩 테스트에서 재귀를 사용하면 좋을까?
코딩 테스트에서 재귀를 활용하는 문제 유형은 보통 분할 정복(Divide and Conquer), 백트래킹(Backtracking), DFS(깊이 우선 탐색) 같은 패턴이 많다.
✅ 1. 분할 정복 (Divide and Conquer)
문제를 더 작은 부분 문제로 나누고, 이를 결합해 해결하는 방식
📌 대표 문제: 이진 탐색 (Binary Search)
def binary_search(arr, target, left, right):
if left > right:
return -1 # 탐색 실패
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, target, left, mid - 1)
else:
return binary_search(arr, target, mid + 1, right)
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7, 0, len(arr) - 1)) # 출력: 3🔹 시간복잡도: O(log N)
✅ 2. 백트래킹 (Backtracking)
모든 경우의 수를 탐색하면서 불가능한 경우를 빠르게 배제하는 방식
📌 대표 문제: N-Queen 문제
def is_safe(board, row, col, n):
for i in range(row):
if board[i] == col or abs(board[i] - col) == row - i:
return False
return True
def solve_n_queens(board, row, n, result):
if row == n:
result.append(board[:])
return
for col in range(n):
if is_safe(board, row, col, n):
board[row] = col
solve_n_queens(board, row + 1, n, result)
def n_queens(n):
result = []
solve_n_queens([-1] * n, 0, n, result)
return result
print(n_queens(4))🔹 시간복잡도: O(N!) (비효율적이지만 백트래킹으로 줄일 수 있음)
✅ 3. DFS (깊이 우선 탐색)
그래프를 탐색할 때 재귀를 사용하면 간결하게 구현 가능하다
📌 대표 문제: DFS 그래프 탐색
def dfs(graph, node, visited):
visited[node] = True
print(node, end=" ")
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(graph, neighbor, visited)
graph = {
1: [2, 3],
2: [4, 5],
3: [6],
4: [],
5: [],
6: []
}
visited = {node: False for node in graph}
dfs(graph, 1, visited) # 출력: 1 2 4 5 3 6🔹 시간복잡도: O(V + E) (V: 노드 수, E: 간선 수)
✅ 4. 조합과 순열 (Combination & Permutation)
모든 경우의 수를 탐색하는 문제에서 재귀가 자주 사용된다.
📌 대표 문제: 순열 (Permutation)
def permute(nums, path=[]):
if not nums:
print(path)
return
for i in range(len(nums)):
permute(nums[:i] + nums[i+1:], path + [nums[i]])
permute([1, 2, 3])🔹 시간복잡도: O(N!)
✅ 5. 분할 정복을 활용한 정렬 (Merge Sort, Quick Sort)
정렬 알고리즘에서도 재귀가 많이 사용된다.
📌 대표 문제: 퀵 정렬 (Quick Sort)
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))🔹 시간복잡도: 평균 O(N log N), 최악 O(N²)
정리 - 유형대표 문제시간복잡도
| 분할 정복 |
이진 탐색, 병합 정렬 | O(log N), O(N log N) |
| 백트래킹 | N-Queen, 모든 경우 탐색 | O(N!) |
| DFS | 그래프 탐색, 미로 탐색 | O(V + E) |
| 조합 & 순열 | 모든 경우 탐색 | O(N!) |
| 정렬 | 퀵 정렬, 병합 정렬 | O(N log N) |