재귀 · 분할정복 — 자기 자신을 부르는 함수

// 팩토리얼 — 가장 쉬운 예
function fact(n) {
  if (n <= 1) return 1;          // ① 기저
  return n * fact(n - 1);        // ② 재귀
}

// 트리·JSON 순회 (실전)
function walk(node, fn) {
  fn(node);
  for (const child of node.children ?? []) walk(child, fn);
}
walk(root, n => console.log(n.name));

// 파일 시스템 순회
async function listAll(dir) {
  const items = await fs.readdir(dir, { withFileTypes: true });
  for (const item of items) {
    const full = path.join(dir, item.name);
    if (item.isDirectory()) await listAll(full);   // 재귀
    else console.log(full);
  }
}

// 머지 정렬 — 분할정복 교과서
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left  = mergeSort(arr.slice(0, mid));   // 나누기
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);                    // 합치기
}
function merge(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    out.push(a[i] <= b[j] ? a[i++] : b[j++]);
  }
  return [...out, ...a.slice(i), ...b.slice(j)];
}
// O(n log n) — log n개 단계 × 각 단계 O(n) 합치기