Recursive 솔루션을 Stack을 사용하여 LeetCode에서 Iterative로 변환하는 방법

발행: 2일 전 (2025년 12월 8일 오후 12:20 GMT+9)

8 min read

원문: Dev.to

Source: Dev.to

Originally published on LeetCopilot Blog

TL;DR

재귀는 함수가 자신을 호출하면서 콜 스택이 지역 상태를 기억하는 방식이다; 반복문으로 변환한다는 것은 그 콜 스택을 직접 만든 명시적 스택으로 시뮬레이션한다는 뜻이다.

핵심 단계

재귀 상태를 식별한다.
각 호출을 스택‑프레임 객체로 바꾼다.
초기 프레임을 푸시한다.
스택이 비어있지 않은 동안 루프를 돈다.
자식들을 새 프레임으로 푸시하면서 확장한다.

재귀 트리와 스택을 나란히 시각화하면 각 프레임이 어떤 정보를 필요로 하는지 훨씬 쉽게 파악할 수 있다.

초보자는 프레임에 충분한 상태(예: 부분 결과나 현재 처리 중인 자식)를 저장하지 않거나, 자식을 잘못된 순서로 푸시해 순회 동작이 바뀌는 실수를 자주 한다.

연습을 통해 재귀와 반복을 서로 교환 가능한 도구로 여기고, 면접관이 반복 버전을 요구할 때 자신감을 가질 수 있다.

Beginner‑Friendly Explanation: What Recursion Really Does

The hidden stack

각 재귀 호출마다:

매개변수와 지역 변수를 프레임에 저장한다.
함수 본문으로 점프한다.

반환될 때 이전 프레임이 중단된 지점부터 다시 실행된다.

다음과 같이 생각할 수 있다:

Call: dfs(root)

Stack (top at bottom):
  [dfs(root)]
    ↳ calls dfs(root.left)
  [dfs(root)]       [dfs(root.left)]
    ↳ calls dfs(root.left.left)
  [dfs(root)] [dfs(root.left)] [dfs(root.left.left)]

베이스 케이스에 도달하면 프레임이 하나씩 스택에서 팝된다.

Iterative idea in one sentence

재귀를 반복으로 변환하려면 그 스택을 직접 제어한다—각 프레임이 무엇을 저장할지, 언제 프레임을 푸시할지, 루프 안에서 어떻게 처리할지를 스스로 결정한다.

Step‑by‑Step Framework: Convert Recursion to Iteration

우리는 이진 트리에서 고전적인 재귀 DFS를 예제로 사용할 것이다.

Step 1: Write or inspect the recursive version

전위 순회 (root → left → right):

def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

핵심 관찰점

호출당 상태: root 노드 레퍼런스.
순서: 현재 노드 → 왼쪽 자식 → 오른쪽 자식.

Step 2: Decide what your “stack frame” holds

이 간단한 DFS에서는 프레임에 노드 자체만 있으면 된다.

보다 복잡한 재귀에서는 프레임에 다음이 필요할 수 있다:

노드 + 부분 결과.
노드 + 현재 처리 중인 자식의 인덱스.
남은 목표 합, 깊이 등 추가 매개변수.

Step 3: Initialize the stack like the first call

첫 번째 재귀 호출은 preorder(root)이므로, 반복 버전의 초기 스택도 이를 흉내 내야 한다:

type Frame = { node: TreeNode | null };

시작하려면 { node: root }를 푸시한다.

Step 4: Loop while the stack is not empty

콜 스택 대신 당신이 루프를 제어한다:

function preorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  if (!root) return result;

  const stack: TreeNode[] = [root]; // 여기서는 프레임이 노드 자체가 된다

  while (stack.length > 0) {
    const node = stack.pop()!;
    result.push(node.val);

    // 자식을 역순으로 푸시 (스택은 LIFO)
    if (node.right) stack.push(node.right);
    if (node.left)  stack.push(node.left);
  }

  return result;
}

push 호출 순서를 이렇게 하면 root → left → right 순서를 유지한다: 마지막에 푸시한 노드가 먼저 팝되기 때문이다. right를 먼저 푸시하고 left를 나중에 푸시하면 left가 먼저 처리된다.

Visual Diagram: Recursion vs Iteration

Recursive DFS (pre‑order)

Call stack (top at bottom):

preorder(A)
  preorder(B)
    preorder(D)
    preorder(E)
  preorder(C)
    preorder(F)

Iterative DFS using a stack

Initial: stack = [A]

Pop A → visit A → push C, B      stack = [C, B]
Pop B → visit B → push E, D      stack = [C, E, D]
Pop D → visit D                  stack = [C, E]
Pop E → visit E                  stack = [C]
Pop C → visit C → push F         stack = [F]
Pop F → visit F                  stack = []

방문 순서는 동일하게 A, B, D, E, C, F가 된다.

More Complex Case: Simulating “Post‑Order” with Explicit States

일부 재귀 함수는 자식들을 처리한 뒤 작업을 수행한다(예: 후위 순회 또는 트리 DP). 이런 경우 각 프레임에 약간의 추가 상태가 필요하다.

Recursive post‑order

def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

Iterative version with a visited flag

type Frame = {
  node: TreeNode;
  visited: boolean; // 이미 자식을 푸시했는가?
};

function postorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  if (!root) return result;

  const stack: Frame[] = [{ node: root, visited: false }];

  while (stack.length > 0) {
    const frame = stack.pop()!;
    const { node, visited } = frame;

    if (visited) {
      // 자식 처리가 끝났으니 이제 노드를 처리
      result.push(node.val);
    } else {
      // 후위 순회: left, right, node
      // 현재 노드를 visited 상태로 다시 푸시
      stack.push({ node, visited: true });
      if (node.right) stack.push({ node: node.right, visited: false });
      if (node.left)  stack.push({ node: node.left, visited: false });
    }
  }

  return result;
}

이 패턴—플래그와 함께 재푸시—은 재귀 없이 “자식 뒤에 작업하기”를 시뮬레이션하는 강력한 방법이다.

Practical Preparation Strategies

Strategy 1: Practice on tree DFS variants

다음 순서대로 연습한다:

전위 순회 (root–left–right).
중위 순회 (left–root–right).
후위 순회 (left–right–root).

각각에 대해:

재귀 버전을 작성한다.
호출당 상태를 식별한다.
프레임 객체 스택을 이용한 반복 버전을 구현한다.

이 과정을 통해 더 복잡한 변환을 위한 탄탄한 기반을 다질 수 있다.

Strategy 2: Convert one real LeetCode problem per week

이미 작성한 재귀 솔루션을 하나 골라서:

작은 예시로 재귀 트리를 그린다.
각 프레임이 기억해야 할 내용을 주석 처리한다.
프레임 객체 스택을 사용해 반복 버전을 작성한다.

패턴을 노트에 기록하거나 DSA learning path에 정리해 두면 면접 전 복습하기 좋다.

Strategy 3: Use tools to visualize stacks when stuck

반복 버전이 재귀와 일치하지 않을 때는 LeetCopilot 같은 도구를 활용해 두 버전을 나란히 단계별로 실행하고 스택 변화를 시각화한다. 이렇게 하면 시뮬레이션이 어디서 어긋나는지 정확히 파악할 수 있다.

Common Mistakes to Avoid

Mistake 1: Not storing enough state in the frame

(…the article continues with additional mistakes…)