재귀와 콜 스택: 트리 모양 데이터 다루기

01. 자기 자신을 부르는 함수

재귀 함수는 두 부분으로 이뤄져요. 더 쪼갤 필요 없이 바로 답할 수 있는 멈추는 조건과, 문제를 조금 작게 만들어 자기 자신에게 맡기는 재귀 호출이에요. 1부터 n까지의 합은 "n + (1부터 n−1까지의 합)"이고, n이 1이면 그냥 1이에요.

function sumTo(n) {
  if (n === 1) return 1;       // 멈추는 조건
  return n + sumTo(n - 1);     // 조금 작은 문제를 자기에게 맡겨요
}

console.log(sumTo(4));   // 10
console.log(sumTo(100)); // 5050

함수를 부르면 자바스크립트는 그 호출의 정보(매개변수, 지역 변수, 돌아갈 자리)를 콜 스택에 한 칸 쌓아요. sumTo(4)는 sumTo(3)의 답을 기다리느라 끝나지 못하고, sumTo(3)은 sumTo(2)를 기다려요. 멈추는 조건에 닿으면 그때부터 위에서부터 하나씩 답을 돌려주며 칸이 빠져요.

멈추는 조건을 빠뜨리거나 조건에 절대 닿지 않으면, 칸이 끝없이 쌓이다가 스택이 넘쳐요. 브라우저는 보통 만 개 안팎에서 멈추고 RangeError를 던져요.

function forever(n) {
  return n + forever(n - 1);   // 멈추는 조건이 없어요
}
forever(3);

02. 트리 데이터: 댓글과 메뉴

합계 같은 문제는 반복문이 더 간단해요. 재귀가 진짜 빛나는 곳은 같은 모양이 안에 또 들어 있는 데이터, 즉 트리예요. 답글 목록 replies 안의 각 댓글이 또 replies를 가지는 댓글 데이터를 보세요. "댓글 목록의 개수 = 각 댓글 1개 + 그 댓글의 답글 목록의 개수"라서 재귀로 그대로 옮겨져요.

const comments = [
  { id: 1, text: '좋은 글이에요', replies: [
    { id: 2, text: '감사해요', replies: [] },
    { id: 3, text: '저도요', replies: [{ id: 4, text: '+1', replies: [] }] },
  ] },
  { id: 5, text: '질문 있어요', replies: [] },
];

function countAll(list) {
  let n = 0;
  for (const c of list) n += 1 + countAll(c.replies); // 빈 배열이면 0이라 여기서 멈춰요
  return n;
}
console.log(countAll(comments)); // 5

// 들여쓰기한 목록으로 펼치기: 깊이를 함께 넘겨요
function flatten(list, depth = 0, out = []) {
  for (const c of list) {
    out.push('  '.repeat(depth) + c.text);
    flatten(c.replies, depth + 1, out);
  }
  return out;
}
console.log(flatten(comments).join('\n'));

여기서는 멈추는 조건이 따로 없어 보이지만, 답글이 없는 댓글의 replies는 빈 배열이라 반복문이 한 번도 돌지 않고 끝나요. 그게 멈추는 조건이에요. 트리를 다루는 재귀는 대개 이렇게 "자식이 없으면 끝"이 멈추는 조건이 돼요.

03. 너무 깊다면 반복문으로

화면에 보이는 메뉴 · 댓글은 깊어야 몇십 단계라 재귀로 충분해요. 하지만 사용자가 만든 데이터처럼 깊이를 믿을 수 없거나 수천 단계가 될 수 있다면 콜 스택이 넘칠 수 있어요. 그때는 "아직 볼 항목" 배열을 직접 들고 반복문으로 돌아요. 콜 스택 대신 내 배열을 스택으로 쓰는 거예요.

const comments = [
  { id: 1, text: '좋은 글이에요', replies: [
    { id: 2, text: '감사해요', replies: [] },
    { id: 3, text: '저도요', replies: [{ id: 4, text: '+1', replies: [] }] },
  ] },
  { id: 5, text: '질문 있어요', replies: [] },
];

function countWithLoop(list) {
  const todo = [...list];           // 아직 볼 댓글
  let n = 0;
  while (todo.length > 0) {
    const c = todo.pop();
    n++;
    todo.push(...c.replies);        // 답글은 나중에 볼 목록에 넣어요
  }
  return n;
}
console.log(countWithLoop(comments)); // 5 — 재귀와 같은 답

재귀 쪽이 더 읽기 쉬우니 기본은 재귀로 쓰고, 깊이가 걱정될 때만 이렇게 바꿔요. JSON.stringify · structuredClone처럼 브라우저가 이미 만들어 둔 기능이 트리를 다 돌아 주는 경우도 많으니, 직접 짜기 전에 찾아봐요.

['홈', '상품', '태블릿']
['홈', '고객센터', '자주 묻는 질문']
null

const menu = {
  name: '홈',
  children: [
    { name: '상품', children: [{ name: '노트북', children: [] }, { name: '태블릿', children: [] }] },
    { name: '고객센터', children: [{ name: '자주 묻는 질문', children: [] }] },
  ],
};

function findPath(node, target) {
  // 여기를 채워요
  return null;
}

console.log(findPath(menu, '태블릿'));
console.log(findPath(menu, '자주 묻는 질문'));
console.log(findPath(menu, '없는 메뉴'));

function findPath(node, target) {
  if (node.name === target) return [node.name];
  for (const child of node.children) {
    const path = findPath(child, target);
    if (path) return [node.name, ...path];
  }
  return null;
}

04. 실전 포인트

• 언제 쓰나요? 댓글 · 메뉴 · 폴더 · 조직도 · 카테고리처럼 같은 모양이 안에 반복되는 트리 데이터를 세고, 펼치고, 찾고, 바꿀 때 써요.
• 대신 쓰는 것: 단순한 합계 · 반복은 반복문이 빠르고 읽기 쉬워요. 깊이를 믿을 수 없으면 배열을 스택으로 쓰는 반복문으로 바꿔요. 서버에서 트리를 평평한 목록(parentId)으로 주는 경우도 많은데, 그대로 다루면 재귀가 필요 없기도 해요.
• 흔한 실수: 멈추는 조건을 빠뜨리거나 문제를 작게 만들지 않아 RangeError가 나는 것, 재귀 호출의 결과를 return하지 않는 것, 같은 하위 문제를 몇 번씩 다시 계산해 느려지는 것(이건 클로저 글의 캐시로 풀어요)이에요.