재귀와 분할

기저 사례

재귀는 언제 멈추는지가 없으면 스택이 넘칩니다. 피보나치면 n<=2, 이분 탐색이면 lo>hi.

점화

f(n) = f(n-1) + f(n-2)처럼 정의하되, 실무에서는 메모이제이션·루프로 바꿉니다.

이분 탐색

정렬된 배열에서 mid를 고르고 절반을 버립니다. 비교 횟수는 대략 log₂ n.

while (lo <= hi) {
  const mid = (lo + hi) >> 1;
  if (arr[mid] === t) return mid;
  if (arr[mid] < t) lo = mid + 1;
  else hi = mid - 1;
}

주의

깊은 재귀는 브라우저·Pyodide 모두 위험합니다. 깊이가 크면 반복으로 바꾸세요.