재귀(Recursion)와 분할정복(Divide & Conquer) 완벽 이해: 원리, 구현, 실전 예제까지

재귀(Recursion)와 분할정복(Divide & Conquer) 완벽 이해: 원리, 구현, 실전 예제까지

재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법이며, 분할정복은 문제를 쪼개서 해결하는 알고리즘 설계 전략입니다.
이 두 개념은 서로 매우 밀접하며, 실제로 합병 정렬, 이진 탐색, 퀵 정렬, 하노이 탑 등 다양한 문제에 활용됩니다.

이번 글에서는 재귀 함수의 구조와 동작 원리, 그리고 분할정복 패턴의 실전 적용법을 함께 알아보겠습니다.

---

✅ 재귀(Recursion)란?

재귀 함수는 자기 자신을 호출하여 문제를 해결하는 함수입니다.
대부분의 재귀 함수는 **종료 조건(Base Case)**이 반드시 존재해야 하며, 문제를 점점 더 단순한 형태로 줄여가야 합니다.

📌 기본 구조

def recursive():
    if 종료조건:
        return
    recursive()

---

🔁 예시: 팩토리얼(Factorial) 함수

반응형

✅ 재귀 방식

def factorial(n):
    if n == 0:
        return 1  # 종료 조건
    return n * factorial(n - 1)

print(factorial(5))  # 출력: 120

✅ 반복문 방식 (비재귀)

def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

---

🚨 재귀 함수 주의점

• 종료 조건이 없으면 무한 루프에 빠짐 (→ RecursionError)
• 함수 호출 스택이 쌓이므로 공간복잡도는 O(n)
• 너무 깊은 호출은 반복문으로 전환하거나 꼬리 재귀 최적화 필요

---

🔨 분할 정복(Divide and Conquer)이란?

큰 문제를 나눠서(subproblem) 해결한 후 다시 합치는 방식의 알고리즘 전략입니다.
재귀와 함께 쓰이며, 다음 3단계로 이루어집니다:

1. 분할(Divide): 문제를 작은 문제로 쪼갠다
2. 정복(Conquer): 작은 문제들을 해결한다 (재귀적으로)
3. 결합(Combine): 결과를 모아서 원래 문제를 해결한다

---

🧪 예시 1: 이진 탐색 (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, mid + 1, right)
    else:
        return binary_search(arr, target, left, mid - 1)

• 분할: 배열을 반으로 나눈다
• 정복: 반쪽에 대해 다시 탐색
• 결합: 재귀 호출 결과 반환

---

🧪 예시 2: 합병 정렬 (Merge Sort)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

• 정렬 알고리즘 중 대표적인 분할정복 기반 알고리즘
• 시간 복잡도: O(n log n)

---

🧠 실전 예제: 피보나치 수열

✅ 재귀 방식 (비효율적)

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

• 시간복잡도: O(2ⁿ) → 매우 비효율적

✅ 메모이제이션(DP) 적용

memo = {}

def fib_dp(n):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_dp(n - 1) + fib_dp(n - 2)
    return memo[n]

• 시간복잡도: O(n)
• 재귀 + 메모이제이션 = 동적 프로그래밍

---

📊 재귀 vs 반복

기준 재귀 방식 반복 방식

코드 간결성	👍 매우 직관적	🟡 조건문 및 변수 관리 필요
성능	🟥 느리고 메모리 소모 큼	👍 빠르고 안정적
스택 사용	함수 호출 스택 사용 (O(n))	스택 없음
위험성	무한루프 가능 (Base Case 중요)	안정적

---

📌 결론 및 요약

• 재귀는 문제를 자기 자신으로 단순화하여 해결하는 기법입니다.
• 분할정복은 문제를 나누고 합쳐서 해결하는 알고리즘 전략이며, 재귀와 자주 함께 쓰입니다.
• 재귀를 사용할 땐 반드시 종료 조건이 있어야 하며, 필요시 메모이제이션으로 최적화할 수 있습니다.
• 실전에서는 성능을 위해 반복문으로 전환하거나, 하이브리드 방식으로 사용하는 경우가 많습니다.

👉 다음 글에서는 **동적 프로그래밍(Dynamic Programming)**의 개념과 패턴, 실전 문제 예제를 집중적으로 다루겠습니다!

---

📚 참고자료 및 출처

• 『Introduction to Algorithms (CLRS)』
• 『파이썬 알고리즘 인터뷰』 (이동욱 저)
• GeeksforGeeks – Recursion and D&C

---

 

재귀, 분할정복, divide and conquer, 재귀함수, 피보나치, merge sort, binary search, 파이썬 알고리즘, 시간복잡도, SEO 최적화 10개