Recursion & Divide-and-Conquer

1. Overview

재귀 및 분할 정복(Recursion & Divide-and-Conquer, RDC)은 복잡한 세상을 단순한 반복의 연쇄로 치환하여 정복하는 '하향식(Top-down) 해결 물리학'의 기초입니다.

아무리 큰 문제도 결국 '더 이상 쪼갤 수 없는 단위(Base Case)'가 모여 만들어집니다. 학습자는 함수가 자기 자신을 물리적으로 호출하며 시스템 스택을 활용하는 **재귀(Recursion)**의 메커니즘을 배웁니다. 또한, 문제를 분할(Divide)하고, 각각 정복(Conquer)한 뒤, 결과를 결합(Combine)하여 전체 해답을 도출하는 분할 정복의 수리적 워크플로우를 익힙니다. 이를 통해 합병 정렬이나 퀵 정렬과 같은 $O(n \log n)$ 급의 고속 알고리즘이 어떻게 탄생했는지에 대한 논리적 해답을 얻습니다.

2. Scope & Boundaries

In-Scope

• Recursive Foundations: Base Case와 Recursive Case의 수리적 분리 논리
• Divide-and-Conquer Workflow: 분할, 정복, 결합 3단계의 물리적 실행 경로
• Sorting Mechanics: Merge Sort, Quick Sort의 내부 분할 물리 및 제자리(In-place) 연산
• Master Theorem: 재귀적 복잡도를 계산하는 $T(n) = aT(n/b) + f(n)$ 수식 모델

Out-of-Scope

• 반복문(Iteration) 위주의 단순 알고리즘 (기초 프로그래밍 영역으로 위임)
• 중복된 부분 문제를 다루는 동적 계획법 (04-03-02 노드에서 분담)

Boundaries

• RDC vs. Dynamic Programming: RDC가 '독립적인' 부분 문제들로 쪼개는 것에 집중한다면, DP(04-03-02)는 '중복된' 부분 문제의 결과를 저장(Memoization)하는 기법에 집중하여 구분합니다.

3. Counterexample

• 단순히 "함수가 자기를 부르는 것"이라 설명하는 것은 RDC 학습이 아닙니다. 재귀가 반복문보다 메모리 오버헤드를 더 많이 유발하는 물리적 이유(스택 프레임 생성)를 시스템 관점에서 증명할 수 있어야 하며, 퀵 정렬에서 최악의 피벗(Pivot) 선택이 왜 $O(n \log n)$ 성능을 **$O(n^2)$**으로 폭락시키는지 물리적 분균형 관점에서 분석하지 못한다면 RDC의 핵심 리스크를 놓친 것입니다.

4. Prerequisites

• Stacks, Queues & Deques (Basic): 함수 호출 스택 기초 이해가 필수입니다. (04-01-03 SQD)
• Complexity Analysis & Big-O (Recommended): 재귀적 시간 복잡도 이해가 권장됩니다. (04-01-04 CAB)

5. Learning Map

1. The Base Case Anchor: 무한 루프의 절벽을 막는 유일한 안전장치 '기초 조건'을 설정합니다.
2. The Stack Layering: 함수가 층층이 쌓였다가 거꾸로 풀려나오는 시스템 물리를 배웁니다.
3. The Splitting Strategy: 문제를 절반씩 혹은 특정 기준으로 절단하는 분할 물리를 익힙니다.
4. The Recursive Victory: 쪼개진 조각들을 정렬된 상태로 이어 붙여 전체를 완성하는 기법을 완성합니다.

6. Learning Topics

Basic

Core: 재귀 함수의 논리 구조 (Recursive Thinking)

• Why to Learn: 복잡한 반복 구조를 수학적으로 명쾌하고 간결하게 표현하기 위해서입니다.
• What to Learn:
  • Base Case: 재귀를 멈추고 값을 반환하는 물리적 종착점
  • Recursive Step: 문제를 더 작은 동일 형태로 전이시키는 논리 물리
  • Factorial & Fibonacci: 재귀적 사고를 훈련하는 가장 기초적인 수리 모델
• How to Learn:
  • 팩토리얼 계산 과정을 종이에 적으며, 호출 시 스택에 쌓이는 인자값들과 반환 시 합쳐지는 과정을 역추적 실습
  • 무한 재귀를 고의로 실행시켜 'Stack Overflow'가 발생하는 하드웨어 경계를 직접 경험
• Implement: 팩토리얼이나 하노이의 탑을 해결하는 기초 재귀 함수

Recommended

Core: 분할 정복 3단계론 (Divide-and-Conquer Paradigm)

• Why to Learn: 대규모 데이터를 한꺼번에 처리하지 않고 $O(\log n)$ 단계로 나누어 처리하는 마법의 속도를 얻기 위함입니다.
• What to Learn:
  • Divide: 문제를 비-중복적 하위 조각으로 분리하는 기법
  • Conquer: 조각이 충분히 작아졌을 때 재귀적으로 해결하는 법
  • Combine: 분절된 해답들을 하나의 논리적 흐름으로 병합하는 물리 과정
• How to Learn:
  • $n$개의 데이터를 반으로 계속 쪼개며 깊이 $\log n$이 도출되는 수리적 원리 분석 실습
  • 합병 정렬(Merge Sort)에서 두 정렬된 리스트를 합치는 과정의 물리적 실행 시간 도출
• Implement: 정렬되지 않은 배열을 반으로 나눠 정렬 후 병합하는 MergeSort

Practical

Core: 고속 정렬과 피벗 전략 (Quick Sort Mechanics)

• Why to Learn: 실제 대부분의 시스템 라이브러리에서 쓰이는 가장 실전적인 분할 정복 알고리즘이기 때문입니다.
• What to Learn:
  • Partitioning: 기준값(Pivot)을 중심으로 메모리를 두 구역으로 재배치하는 물리 연산
  • Pivot Selection: 랜덤 피벗이나 Median-of-three를 통한 최악의 경우 방지 물리
  • Tail Recursion Optimization: 스택 점유 메모리를 줄이기 위한 컴파일러 급의 최적화 이해
• How to Learn:
  • 퀵 정렬의 파티셔닝 과정을 배열 상에서 포인터 두 개($i, j$)가 움직이는 물리 동선으로 그려보기 실습
  • 이미 정렬된 배열을 퀵 정렬로 돌렸을 때 왜 성능이 최악이 되는지 수리적으로 증명
• Implement: 피벗을 선택하여 제자리(In-place)에서 구역을 나누는 고성능 QuickSort

Advanced

Core: 재귀적 복잡도 정복 (Asymptotic Convergence)

• Why to Learn: 내 재귀 알고리즘이 실제로 얼마나 빠른지 수학적으로 엄격하게 보증하기 위해서입니다.
• What to Learn:
  • Recursion Tree Method: 각 층별 작업량을 합산하여 복잡도를 도출하는 기하학적 분석
  • Master Theorem Case 1, 2, 3: 문제 분할 수와 비용 함수 사이의 우열에 따른 최종 복잡도 등급 판정
  • Closest Pair of Points: 평면 상의 점들을 분할 정복으로 $O(n^2)$에서 $O(n \log n)$으로 줄이는 응용 물리
• How to Learn:
  • 마스터 정리를 이용해 Merge Sort와 Binary Search의 복잡도를 공식에 대입하여 즉시 산출 훈련 실습
  • 행렬 곱셈을 분할 정복으로 가속하는 슈트라센(Strassen) 알고리즘의 수리적 아이디어 분석
• Implement: 마스터 정리의 형식을 입력받아 예상 Big-O를 출력해 주는 간단한 계산기

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 중 적절한 알고리즘을 제안할 수 있는 가?