Recursion & Divide-and-Conquer

1. Overview

재귀와 분할 정복(Recursion & Divide-and-Conquer)은 복잡한 큰 문제를 동일한 구조의 더 작은 하위 문제로 재귀적으로 쪼개어, 기저 조건(Base Case)에서 즉각 해결하고 결과를 합쳐(Combine) 올라오는 인류가 발명한 가장 강력하고 우아한 알고리즘 패러다임입니다.

학습자는 재귀 함수가 호출될 때마다 스택 프레임이 쌓이는 콜 스택의 물리적 실체와 스택 오버플로우(Stack Overflow)의 경계를 뜯어봅니다. 나아가 분할 정복(Divide-and-Conquer)의 3단계(Divide → Conquer → Combine)가 합병 정렬(Merge Sort O(n log n)), 퀵 정렬(Quick Sort O(n log n) avg), 이진 탐색(Binary Search O(log n))을 어떻게 탄생시켰는지 해부합니다. 마지막으로 단순 재귀의 O(2ⁿ) 지수 폭탄을 꼬리 재귀(Tail Recursion) 최적화와 반복(Iteration) 변환으로 선형(O(n)) 또는 상수(O(1)) 공간으로 제거하는 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 재귀 기본 물리 (Recursion Mechanics): 기저 조건(Base Case), 재귀 케이스(Recursive Case), 콜 스택 프레임, 스택 오버플로우, 재귀 트레이스(Trace).
• 분할 정복 패러다임 (D&C): 합병 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색(Binary Search), 카라츠바 곱셈(Karatsuba), 스트라센 행렬 곱셈(Strassen).
• 재귀 최적화 (Recursion Optimization): 꼬리 재귀(Tail Recursion, TCO), 메모이제이션(Memoization, Top-Down DP 도입부), 반복 변환(Iteration Conversion).
• 백트래킹 구분 (Backtracking Boundary): 재귀 ≠ 백트래킹, 순열/조합 생성에서의 분기.

Out-of-Scope

• 동적 프로그래밍(DP): 중복 하위 문제(Overlapping Subproblems)를 메모이제이션/테이블로 해결하는 패러다임 $\rightarrow$ 04-03-02. Dynamic Programming 영역.
• 백트래킹(Backtracking): 상태 공간 탐색에서 조건 불만족 시 되돌아가는 패러다임 $\rightarrow$ 04-03-04. Backtracking & State Space 영역.

Boundaries

• D&C vs DP: 분할 정복은 하위 문제들이 서로 독립적이어서 결과를 공유/재사용할 필요 없는 경우(합병 정렬: 각 절반은 서로 간섭하지 않음)에 적합합니다. DP는 하위 문제들이 겹치고(Overlapping) 결과를 재사용해야 할 때(피보나치: fib(4)=fib(3)+fib(2), fib(3)=fib(2)+fib(1) → fib(2) 중복 계산) 필수적입니다.

3. Counterexample

• 재귀 피보나치의 O(2ⁿ) 지수 폭탄 (Naive Fibonacci Explosion): fib(n) = fib(n-1) + fib(n-2) 순진한 재귀로 fib(50) 을 계산하는 코드. fib(50)은 fib(49)와 fib(48)을 각각 독립적으로 호출하고, 각각은 또 두 개를 호출하여 호출 트리가 2^50 ≈ 10^15 번의 함수 호출로 폭발합니다. 10억(10^9) 연산/초 CPU에서 100만 초 = 11.5일이 걸립니다. 메모이제이션 한 줄로 O(n)으로 단축됩니다.
• 분할 정복 Merge Sort의 Combine 단계 메모리 함정 (Merge Sort Memory): "Merge Sort가 O(n log n)이니까 메모리도 효율적이겠지"라는 오해. Merge 단계에서 두 정렬된 배열을 합치려면 임시 배열(보조 공간)이 O(n) 필요합니다. n=100만이면 합병 정렬은 O(n) = 100만 × 4Byte = 4MB 추가 메모리를 반드시 요구합니다. In-place Heap Sort(O(1) 추가 공간)나 In-place Quick Sort를 원하면 Merge Sort를 포기해야 하는 트레이드오프입니다.

4. Prerequisites

• 스택 자료구조 (Basic): 재귀 호출이 콜 스택을 사용하므로 LIFO 스택 개념이 필요합니다. (04-01-03 Stacks & Queues)
• 점화식과 마스터 정리 (Recommended): 재귀 알고리즘의 복잡도 분석에 필수. (04-01-04 Complexity Analysis)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 호출 스택의 쌓임과 기저 조건의 구원, 재귀 역학 (Recursion Mechanics)

• Why to Learn: 재귀를 쓸 때마다 "이게 무한루프는 아닌가?", "메모리는 얼마나 쓰나?"라는 불안을 제거하고, 재귀 함수의 실행 흐름과 콜 스택 소비를 정확히 예측하는 디버깅 근육을 만들기 위함입니다.
• What to Learn:
  • Concepts: 기저 조건(Base Case), 재귀 케이스(Recursive Case), 재귀 트레이스(Trace), 콜 스택 깊이 = O(n)(스택 오버플로우 깊이).
  • Skills: 재귀 트리 그리기, 수학적 귀납법으로 재귀의 정확성 증명.
  • Tools: Python sys.setrecursionlimit(), 재귀 트레이서 데코레이터.
• How to Learn:
  • 1단계: factorial(5) 실행 트레이스. factorial(5) → 5 * factorial(4) → 5*4*factorial(3) → ... → 5*4*3*2*1*factorial(0) → 1 (기저). 결과가 역방향으로 fold되며 올라오는 콜 스택 unfold 역학을 해부합니다.
  • 2단계: 기저 조건 없는 bad_fib(n) = bad_fib(n-1) + bad_fib(n-2) 코드. n이 1보다 작아지지 않는 입력으로 무한 재귀가 발생하여 Python RecursionError: maximum recursion depth exceeded 스택 오버플로우 폭발을 뜯어봅니다.
• Implement: 파이썬 recursion_tracer 데코레이터. 재귀 함수에 붙이면 → func(arg) 들어갈 때, ← func(arg) = return_val 나올 때를 들여쓰기 레벨로 콘솔 출력. factorial(5) 실행 시 5-depth 콜 스택이 시각화되는 트레이서 증명.

Recommended

Core Topic 02: 반으로 쪼개 각자 정렬하고 합치기, 합병 정렬 (Merge Sort)

• Why to Learn: 안정 정렬(Stable Sort)의 대표주자이자, TimSort(Python/Java 내장 정렬), 외부 정렬(External Sort), 연결 리스트 정렬의 핵심인 Merge Sort의 분할 정복 3단계를 완전히 장악하기 위함입니다.
• What to Learn:
  • Concepts: Divide(반으로 분할), Conquer(재귀 정렬), Combine(병합 연산), 안정 정렬(Stable), O(n log n) 시간 + O(n) 공간.
  • Skills: 연결 리스트 Merge Sort(In-place O(1) 공간), 외부 정렬(External Sort, 디스크 K-way Merge).
  • Tools: Python sorted() 내부 TimSort 분석.
• How to Learn:
  • 1단계: [38,27,43,3,9,82] → [38,27,43]+[3,9,82] → [38]+[27,43] + ... (Divide). 기저: 크기 1이면 그대로 리턴. Combine: [27,38,43]와 [3,9,82]를 두 포인터로 병합 → [3,27,38,43,9,82]... → [3,9,27,38,43,82] 역학을 해부합니다.
  • 2단계: 점화식 T(n) = 2T(n/2) + O(n). 마스터 정리 Case 2로 T(n) = O(n log n) 증명. log n 레벨이 있고 각 레벨에서 O(n) 병합 비용이 드는 재귀 트리를 뜯어봅니다.
• Implement: 파이썬 merge_sort(arr) 구현. Divide: mid=len(arr)//2; left=arr[:mid]; right=arr[mid:]. Conquer: left=merge_sort(left); right=merge_sort(right). Combine: 두 포인터 병합. 1000개 랜덤 배열 정렬 후 sorted() 결과와 assert 비교.

Practical

Core Topic 03: 피벗의 경계와 제자리 분할, 퀵 정렬 (Quick Sort & Partition)

• Why to Learn: 실제 C++ std::sort, Java Arrays.sort(int[]), Python 내부 IntroSort의 핵심으로 쓰이는 퀵 정렬의 Partition 역학과, 최악 케이스(O(n²))를 Randomized Pivot으로 회피하는 기법을 장악하기 위함입니다.
• What to Learn:
  • Concepts: Lomuto Partition / Hoare Partition, 피벗 선택(랜덤/중간 값), 최악 케이스 O(n²), 평균 O(n log n), In-place O(log n) 스택.
  • Skills: 랜덤 피벗(Randomized Quicksort), 3-Way Partition(Dutch National Flag, 중복 원소), 꼬리 재귀 최적화 적용.
  • Tools: C++ __introsort_loop, Python timsort.
• How to Learn:
  • 1단계: Lomuto Partition: 피벗=마지막 원소. 두 포인터 i, j로 스캔하며 arr[j] < pivot이면 arr[i]와 교환 후 i++. 루프 끝에 피벗을 arr[i]에 배치. 결과: 피벗 왼쪽 < 피벗 ≤ 오른쪽의 물리를 해부합니다.
  • 2단계: 정렬된 배열 [1,2,3,4,5]에 Naive 퀵소트(피벗=마지막)를 적용하면 항상 1개+나머지로 분할되어 O(n²) 최악이 발생. 랜덤 피벗으로 이를 회피하는 Randomized Quick Sort를 뜯어봅니다.
• Implement: 파이썬 quick_sort(arr, lo, hi). Lomuto Partition 구현. [5,3,8,6,1,9,2,7] 정렬 각 단계에서 피벗 위치와 배열 상태 출력. 추가로 random.shuffle(arr) 후 정렬하여 편향 입력에서의 최악 케이스를 Randomized Pivot으로 O(n log n)로 복구하는 시간 비교.

Advanced

Core Topic 04: 꼬리 호출 최적화와 반복 변환, 재귀의 탈출 (Tail Recursion & Iteration Conversion)

• Why to Learn: 함수형 언어(Haskell, Elixir)와 Scheme, 일부 Python/JavaScript 최적화에서 재귀를 스택 오버플로우 없이 무한히 실행하는 꼬리 재귀 최적화(TCO)의 원리를 꿰뚫고, 모든 재귀를 명시적 스택 반복으로 변환하는 기법을 확보하기 위해서입니다.
• What to Learn:
  • Concepts: 꼬리 위치(Tail Position), 꼬리 재귀(Tail Recursion), TCO(Tail Call Optimization), Continuation-Passing Style(CPS).
  • Skills: 누산기(Accumulator) 패턴으로 재귀를 꼬리 재귀로 변환, 명시적 스택(while + stack)으로 반복 변환.
  • Tools: Python은 TCO를 지원하지 않음(sys.setrecursionlimit), Scheme/Haskell의 TCO 지원.
• How to Learn:
  • 1단계: 꼬리 재귀 변환: factorial(n) = n * factorial(n-1) (비꼬리 재귀: 리턴 후 n*가 남아있어 스택 프레임 유지). → factorial_tail(n, acc=1) = factorial_tail(n-1, n*acc) (꼬리 재귀: 리턴값이 그대로 다음 호출 인자가 되어 스택 프레임이 재사용). 누산기 패턴을 해부합니다.
  • 2단계: 명시적 스택 변환: 재귀 DFS → while stack: node = stack.pop(); stack.extend(node.children) 형태로, 재귀 콜 스택을 프로그래머가 직접 힙에 만든 리스트로 시뮬레이션하는 반복 변환을 뜯어봅니다.
• Implement: 파이썬 factorial_tail(n, acc=1) (꼬리 재귀 형태 변환, Python은 TCO 미지원이므로 동일 동작 확인). 재귀 DFS(트리 순회)를 명시적 스택 while 루프로 변환하여 n=10000 깊이에서도 RecursionError 없이 동작하는 반복 DFS 구현 증명.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Engineering Foundations / Computing Foundations (Recursion) — Recursive context.
• [P1] CS2023 - AL/Algorithms and Complexity (Divide-and-Conquer) — Core requirements.

Secondary

• [Introduction to Algorithms (CLRS)] Cormen — Formal proofs of D&C and Master Theorem.
• [Algorithms] Robert Sedgewick — Quick/Merge sort visualizations.

Industry

• [CPP Reference: std::sort (IntroSort)] — Real-world hybrid sorting.
• [Python: Timsort (Merge & Insertion Hybrid)] — Industry sorting standards.

9. Final Checklist

Primary

• '기초 조건(Base case)'이 누락된 재귀 함수가 물리적으로 왜 시스템 스택 오버플로우를 유발하는지 설명 가능한가? (P1)
• 합병 정렬(Merge Sort)의 전체 시간 복잡도가 왜 $O(n \log n)$이 되는지 그 '분할 층'과 '병합 비용'의 관계로 입증할 수 있는 가? (P1)

Secondary

• 퀵 정렬(Quick Sort)의 평균 성능은 최상이지만, 최악의 경우를 방지하기 위해 어떤 물리적 '피벗 선택' 전략이 필요한지 소통 가능한가?
• 재귀 알고리즘을 반복문(Iteration)으로 변환했을 때 얻는 메모리 상의 물리적 이점을 도출할 수 있는 가?

Industry

• 브라우저 엔진의 렌더링 트리 탐색이나 컴파일러의 구문 분석 시 재귀가 물리적으로 어떻게 활용되는지 기술할 수 있는 가? (SFIA)
• 대규모 데이터 정렬 시스템 설계 시, 안정성(Stability)이 필요한지 여부에 따라 Merge와 Quick 중 적절한 알고리즘을 제안할 수 있는 가?