재귀 (Recursion)

개념

함수가 자기 자신을 호출하는 프로그래밍 기법

큰 문제를 작은 문제로 나누어 해결

---

재귀의 구조

필수 요소

1. Base Case (기저 조건)

   • 재귀를 멈추는 조건
   • 없으면 무한 루프 발생

2. Recursive Case (재귀 조건)

   • 자기 자신을 호출하는 부분
   • 문제를 작게 만들어야 함

def recursive_function(n):
    # Base Case
    if n == 0:
        return 1
 
    # Recursive Case
    return n * recursive_function(n - 1)

---

기본 예제

1. 팩토리얼 (Factorial)

def factorial(n):
    # Base Case
    if n <= 1:
        return 1
 
    # Recursive Case
    return n * factorial(n - 1)
 
# 테스트
print(factorial(5))  # 120 (5 * 4 * 3 * 2 * 1)
 
# 호출 과정:
# factorial(5) = 5 * factorial(4)
#              = 5 * 4 * factorial(3)
#              = 5 * 4 * 3 * factorial(2)
#              = 5 * 4 * 3 * 2 * factorial(1)
#              = 5 * 4 * 3 * 2 * 1
#              = 120
 
# 시간복잡도: O(n)
# 공간복잡도: O(n) - 호출 스택

---

2. 피보나치 수열

def fibonacci(n):
    # Base Case
    if n <= 1:
        return n
 
    # Recursive Case
    return fibonacci(n - 1) + fibonacci(n - 2)
 
# 테스트
print(fibonacci(6))  # 8 (0, 1, 1, 2, 3, 5, 8)
 
# 시간복잡도: O(2^n) - 매우 비효율적!
# 공간복잡도: O(n)

문제점: 같은 계산을 반복 → 메모이제이션으로 해결

# 메모이제이션 사용
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]
 
# 테스트
print(fibonacci_memo(6))  # 8
 
# 시간복잡도: O(n)
# 공간복잡도: O(n)

---

3. 최대공약수 (GCD)

def gcd(a, b):
    # Base Case
    if b == 0:
        return a
 
    # Recursive Case (유클리드 호제법)
    return gcd(b, a % b)
 
# 테스트
print(gcd(48, 18))  # 6
 
# 호출 과정:
# gcd(48, 18) = gcd(18, 12)
#             = gcd(12, 6)
#             = gcd(6, 0)
#             = 6
 
# 시간복잡도: O(log min(a, b))

---

4. 거듭제곱

# 일반 재귀
def power(x, n):
    if n == 0:
        return 1
    return x * power(x, n - 1)
 
# 분할 정복 (더 효율적)
def power_fast(x, n):
    if n == 0:
        return 1
 
    half = power_fast(x, n // 2)
 
    if n % 2 == 0:
        return half * half
    else:
        return half * half * x
 
# 테스트
print(power_fast(2, 10))  # 1024
 
# 시간복잡도: O(log n)
# 공간복잡도: O(log n)

핵심: 분할 정복으로 O(n) → O(log n) 최적화

---

재귀 vs 반복문

재귀로 작성

def sum_recursive(n):
    if n == 0:
        return 0
    return n + sum_recursive(n - 1)
 
print(sum_recursive(5))  # 15

반복문으로 변환

def sum_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total
 
print(sum_iterative(5))  # 15

비교

특성	재귀	반복문
가독성	높음 (간결)	낮음
성능	낮음 (함수 호출 오버헤드)	높음
메모리	높음 (스택)	낮음
디버깅	어려움	쉬움

---

재귀를 사용하는 자료구조

1. 리스트 합계 구하기

def sum_list(arr):
    # Base Case
    if not arr:
        return 0
 
    # Recursive Case
    return arr[0] + sum_list(arr[1:])
 
# 테스트
print(sum_list([1, 2, 3, 4, 5]))  # 15

---

2. 리스트 뒤집기

def reverse_list(arr):
    # Base Case
    if len(arr) <= 1:
        return arr
 
    # Recursive Case
    return [arr[-1]] + reverse_list(arr[:-1])
 
# 테스트
print(reverse_list([1, 2, 3, 4, 5]))  # [5, 4, 3, 2, 1]

---

3. 중첩 리스트 평탄화

def flatten(arr):
    result = []
 
    for item in arr:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
 
    return result
 
# 테스트
nested = [1, [2, 3], [4, [5, 6]], 7]
print(flatten(nested))  # [1, 2, 3, 4, 5, 6, 7]

---

자주 나오는 문제 유형

1. 하노이의 탑

문제: N개의 원판을 다른 기둥으로 옮기기

def hanoi(n, start, end, aux):
    if n == 1:
        print(f"{start} -> {end}")
        return
 
    # 1. n-1개를 보조 기둥으로 이동
    hanoi(n - 1, start, aux, end)
 
    # 2. 가장 큰 원판을 목표 기둥으로 이동
    print(f"{start} -> {end}")
 
    # 3. n-1개를 목표 기둥으로 이동
    hanoi(n - 1, aux, end, start)
 
# 테스트
hanoi(3, 'A', 'C', 'B')
# A -> C
# A -> B
# C -> B
# A -> C
# B -> A
# B -> C
# A -> C
 
# 시간복잡도: O(2^n)
# 이동 횟수: 2^n - 1

핵심: 문제를 작게 나누어 재귀적으로 해결

---

2. 부분집합 생성

문제: 집합의 모든 부분집합 생성

def subsets(nums):
    result = []
 
    def backtrack(start, path):
        result.append(path[:])
 
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
 
    backtrack(0, [])
    return result
 
# 테스트
print(subsets([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
 
# 시간복잡도: O(2^n)
# 공간복잡도: O(n)

핵심: 각 원소를 포함/불포함하는 경우로 분기

---

3. 순열 생성

문제: 주어진 배열의 모든 순열 생성

def permutations(nums):
    result = []
 
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
 
        for i in range(len(remaining)):
            backtrack(path + [remaining[i]],
                     remaining[:i] + remaining[i+1:])
 
    backtrack([], nums)
    return result
 
# 테스트
print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
 
# 시간복잡도: O(n!)

핵심: 각 위치에 올 수 있는 원소를 재귀적으로 선택

---

4. 조합 생성

문제: N개 중 K개를 선택하는 모든 조합

def combinations(nums, k):
    result = []
 
    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
 
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
 
    backtrack(0, [])
    return result
 
# 테스트
print(combinations([1, 2, 3, 4], 2))
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
 
# 시간복잡도: O(C(n, k))

핵심: 순열과 달리 start 인덱스로 중복 방지

---

5. 문자열 분할

문제: 문자열을 회문(palindrome)으로만 분할하는 모든 경우

def partition_palindrome(s):
    result = []
 
    def is_palindrome(string):
        return string == string[::-1]
 
    def backtrack(start, path):
        if start == len(s):
            result.append(path[:])
            return
 
        for end in range(start + 1, len(s) + 1):
            substring = s[start:end]
            if is_palindrome(substring):
                path.append(substring)
                backtrack(end, path)
                path.pop()
 
    backtrack(0, [])
    return result
 
# 테스트
print(partition_palindrome("aab"))
# [['a', 'a', 'b'], ['aa', 'b']]
 
# 시간복잡도: O(n * 2^n)

핵심: 가능한 모든 분할 지점에서 재귀 호출

---

추천 연습 문제

기초

• 백준 10870번 - 피보나치 수 5
• 백준 10872번 - 팩토리얼
• 백준 2447번 - 별 찍기 - 10

중급

• 백준 11729번 - 하노이 탑 이동 순서
• LeetCode 78 - Subsets
• LeetCode 46 - Permutations
• LeetCode 77 - Combinations

고급

• LeetCode 131 - Palindrome Partitioning
• 백준 1914번 - 하노이 탑
• 백준 1629번 - 곱셈

---

핵심 요약

개념	설명
Base Case	재귀를 멈추는 조건 (필수!)
Recursive Case	자기 자신을 호출
메모이제이션	중복 계산 방지
분할 정복	문제를 작게 나누어 해결

---

재귀 작성 팁

1. Base Case부터 생각

def recursive_function(n):
    # 1단계: Base Case 먼저 작성
    if n == 0:
        return something
 
    # 2단계: Recursive Case 작성
    return recursive_function(n - 1)

2. 작은 예제로 테스트

• n=0, n=1, n=2 등 작은 값으로 확인
• 호출 과정을 종이에 그려보기

3. 메모이제이션 고려

# 중복 계산이 많은 경우
def function(n, memo={}):
    if n in memo:
        return memo[n]
 
    # 계산
    result = ...
    memo[n] = result
    return result

4. 꼬리 재귀 최적화 (Tail Recursion)

# 일반 재귀
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
 
# 꼬리 재귀 (누적값 사용)
def factorial_tail(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail(n - 1, n * acc)

---

재귀 vs 반복문 선택 가이드

재귀가 적합한 경우

• 트리/그래프 순회
• 분할 정복 알고리즘
• 백트래킹 문제
• 문제 구조가 재귀적인 경우

반복문이 적합한 경우

• 단순 반복
• 성능이 중요한 경우
• 메모리 제약이 있는 경우
• Python의 재귀 깊이 제한 (기본 1000)

Python 재귀 깊이 늘리기

import sys
sys.setrecursionlimit(10**6)  # 백만으로 증가

주의: 너무 크게 설정하면 스택 오버플로우 발생 가능