Top-Down 방식의 재귀(recursion)를 Bottom-Up 방식의 반복문(iteration)으로 변환하기

재귀(recursion)를 반복문(iteration)으로 바꾸는 것은 “재귀를 수동으로 스택으로 구현”하거나, “재귀의 흐름을 반복문으로 흐르게 만드는 방식”입니다. 이 과정은 컴퓨터가 호출 스택을 활용해 함수를 호출하는 구조를 우리가 직접 명시적으로 처리하는 것으로 이해하면 됩니다.

 

 

 

---

목적

재귀 → 반복문으로 변환하는 이유는 다음과 같습니다.

 

• 스택 오버플로우 방지

• 성능 최적화

• 더 명시적이고 디버깅이 쉬운 코드

 

 

 

---

재귀 → 반복문 변환하기

 

 1단계: 재귀 함수의 핵심 구조 파악

 

아래 예시 코드에 해당하는 1로 만들기 (Top-Down) 문제의 재귀구조

[백준 #1463] 1로 만들기

 

int makeOne(int x) {
    if (x == 1) return 0;

    if (DP[x] != -1) return DP[x];

    DP[x] = makeOne(x - 1) + 1;

    if (x % 2 == 0) DP[x] = Math.min(DP[x], makeOne(x / 2) + 1);
    if (x % 3 == 0) DP[x] = Math.min(DP[x], makeOne(x / 3) + 1);

    return DP[x];
}

 

➡ 이 재귀는 큰 문제 → 작은 문제로 내려가고(x에 해당하는 값을 알기 위해 이보다 작은 값인 x/2 또는 x/3에 해당하는 값을 알아야 하는 상황), 계산한 값을 DP에 저장하여 중복 호출을 피합니다.

 

---

 

2단계: 호출 순서를 확인 → 작은 값부터 올라감

위 코드에 해당하는 Top-Down 재귀는 예를들어 x를 10으로 가정할 때, 아래처럼 호출됩니다

makeOne(10) → makeOne(9) → makeOne(8) → ... → makeOne(1)

 

➡ 반복문에서는 이 순서를 반대로 1 → 2 → … → 10으로 올라가며 DP[i]를 채워야 합니다.

 

---

 

3단계: 반복문으로 변환

DP[1] = 0;

for (int i = 2; i <= X; i++) {
    DP[i] = DP[i - 1] + 1;

    if (i % 2 == 0) DP[i] = Math.min(DP[i], DP[i / 2] + 1);
    if (i % 3 == 0) DP[i] = Math.min(DP[i], DP[i / 3] + 1);
}

 

 

 

---

또다른 예시: 피보나치 수열

Top-Down 방식(재귀)일 때,

f(n) = f(n-1) + f(n-2)

 

Bottom-Up 방식(반복문)일 때,

for (int i = 2; i <= n; i++) f[i] = f[i-1] + f[i-2]