재귀와 분할정복

재귀(Recursion)는 함수가 자신을 호출하는 프로그래밍 기법입니다. 복잡한 문제를 해결할 때 문제를 작게 쪼개고, 이를 반복적으로 해결하는 방식으로 작동합니다. 재귀는 특히 구조적으로 반복이 필요한 문제를 간결하게 표현할 수 있는 장점이 있습니다.

재귀의 주요 구성 요소

• 기저 조건(Base Case): 재귀 호출이 종료되는 조건입니다. 기저 조건이 충족되지 않으면 무한 재귀에 빠질 수 있기 때문에, 종료 조건을 반드시 설정해야 합니다.
• 재귀 호출(Recursive Call): 문제를 더 작은 문제로 분할하여 함수를 다시 호출하는 부분으로, 이 과정이 반복됩니다.

재귀의 특징

• 재귀 호출 시 스택에 각 호출이 쌓이게 됩니다. 각 호출이 종료될 때 스택에서 제거됩니다.
• 재귀 함수는 기본적으로 함수 호출의 깊이에 따라 메모리를 많이 사용할 수 있어, 스택 오버플로우(Stack Overflow)를 주의해야 합니다.

재귀를 사용하는 것은 문제를 간결하고 직관적으로 표현할 수 있는 장점이 있지만, 주의할 점도 있습니다.

재귀의 장점

• 재귀적 구조를 사용하면 문제를 간단히 표현할 수 있어 코드 가독성이 향상됩니다.
• 복잡한 반복 작업을 간결하게 구현할 수 있어 재귀적 관계를 활용하는 문제에 적합합니다.

재귀의 단점

• 재귀 호출 시 스택에 함수 호출이 쌓이기 때문에 메모리 사용량이 많아질 수 있습니다.
• 재귀가 깊어질수록 스택 오버플로우가 발생할 수 있어 기저 조건 설정에 주의해야 합니다.

분할정복은 문제를 더 작은 하위 문제로 나눈 뒤, 각각을 재귀적으로 해결하고 그 결과를 합쳐 전체 문제를 해결하는 전략입니다. 주로 정렬 알고리즘(예: 병합 정렬, 퀵 정렬)에서 사용됩니다.

분할정복의 3단계

• 분할(Divide): 문제를 더 작은 부분 문제로 나눕니다.
• 정복(Conquer): 각 부분 문제를 재귀적으로 해결합니다.
• 결합(Combine): 해결된 부분 문제의 결과를 결합하여 전체 문제의 해답을 구합니다.

분할정복이 사용되는 알고리즘 예시

• 병합 정렬: 배열을 절반으로 분할해 각 부분을 정렬하고, 최종적으로 결합하여 전체 배열을 정렬합니다. 시간 복잡도는 O(N log N)입니다.
• 퀵 정렬: 피벗을 기준으로 배열을 분할하고, 재귀적으로 각 부분을 정렬하여 결합합니다. 평균 시간 복잡도는 O(N log N)이지만 최악의 경우 O(N^2)입니다.

문제 설명: 정수 n이 주어졌을 때, n! (팩토리얼)을 재귀를 사용해 계산하는 함수를 작성하세요.

Python 코드 예제:
def factorial(n):
    if n == 1:  # 기저 조건
        return 1
    return n * factorial(n - 1)  # 재귀 호출

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

설명: factorial 함수는 n == 1일 때 재귀 호출을 종료하며, 이를 기저 조건으로 설정합니다. 이후 n * factorial(n - 1)을 반복하며 결과를 계산합니다.