재귀와 이분 탐색

재귀의 세 요소

1. 기저 사례 (base): 더 쪼개지 않고 끝나는 조건
2. 점화: 더 작은 같은 문제로 환원
3. 진행: 반드시 기저로 향함 (무한 재귀 금지)

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

재귀 = 콜스택

매 호출이 스택 프레임을 씁니다. 깊이 n이면 공간 O(n), 한도가 있으면 런타임 오류가 납니다.
가능하면 반복+명시 스택으로 바꿀 수 있는지 보세요.

분할 정복 감각

문제를 반으로 나누어 각각 풀고 합칩니다. 정렬(머지)·이분 탐색이 대표입니다.

이분 탐색 템플릿

정렬된 배열에서 목표를 찾거나, “조건을 만족하는 최소/최대”를 찾습니다.

function lowerBound(a, target) {
  let lo = 0, hi = a.length; // half-open [lo, hi)
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo; // target 이상인 첫 위치
}

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

경계를 손으로

이분 탐색 버그의 90%는 mid 갱신과 lo/hi 부등호입니다.
길이 0, 1, 2인 배열로 시뮬레이션하세요.

매개변수 이분 (맛보기)

배열이 아니라 답의 후보 구간에 이분을 걸 수 있습니다.
“용량 X면 가능한가?”가 단조이면 check(mid)로 이분합니다. 고급 주제이니, 먼저 배열 이분을 익히세요.

재귀 vs 이분

이분 탐색도 재귀로 쓸 수 있지만, 실무·테스트에서는 반복 while이 안전합니다.

복잡도

이분 탐색: 시간 O(log n), 추가 공간 O(1) (반복).
재귀 이분이면 콜스택 O(log n).