C# - 재귀호출을 스택 자료구조와 반복문을 이용해 대체하는 방법
미리 말씀드리지만 이 글은 다음의 글을 제맘대로 번역한 것입니다. (번역이라고 말하기 좀 그렇군요. 그냥 그 글을 기반으로 썼다고 하는 편이 맞겠지요. ^^)
How to replace recursive functions using stack and while-loop to avoid the stack-overflow
; http://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and
사실 자료구조 공부를 좀 하신 분은 위의 글이 말하는 내용에 대해 이미 알고 계실 텐데요. 그래도 코드와 함께 이해하기 쉽게 글이 쓰여졌기 때문에 공유 차원에서 번역해 봅니다. ^^
재귀호출은 잘 쓰면 로직이 깔끔해지지만, 한 가지 단점이라면 깊이가 증가하는 경우 stack-overflow 예외가 발생할 수 있습니다. (윈도우 프로그램의 경우 기본 스레드 스택 크기는 1MB입니다.)
물론 스레드 스택 크기를 늘림으로써 경우에 따라 스택오버플로우 예외를 빗겨갈 수는 있지만 근본적인 해결책은 되지 않습니다. 따라서, 재귀호출을 반복문으로 변환할 줄 아는 것이 도움이 될 수 있는데요.
이제부터 재귀호출로 작성된 피보나치 수열 메서드를 10단계의 작업을 거쳐 반복문으로 바꾸는 방법을 소개할텐데, "
How to replace recursive functions using stack and while-loop to avoid the stack-overflow" 원문의 경우 C/C++ 언어로 했지만 이 글에서는 C#으로 합니다.
즉, 재귀호출로 작성된 다음의 코드를 10단계로 나눠 반복문으로 바꿀 것입니다.
namespace RecursiveToLoopSamplesCS
{
class BinaryRecursion
{
public static int FibNum(int n)
{
if (n < 1)
{
return -1;
}
if (1 == n || 2 == n)
{
return 1;
}
int addVal = FibNum(n - 1);
addVal += FibNum(n - 2);
return addVal;
}
}
}
참고로, 재귀호출은 유형별로 Linear, Tail, Binary, Nested로 나뉘는데 이 글의 예제로 사용되는 FibNum 메서드는 Binary Recursion에 해당합니다. 그 외 자세한 사항은 다음의 글을 참고하세요. ^^
Type of Recursion
; http://proneer.tistory.com/231
그럼, 한 단계씩 따라가 볼까요? ^^
첫 번째 단계
재귀 호출 메서드에서 사용되는 값의 상태를 보관하는 용도로 "Snapshot" 구조체를 하나 만듭니다. 이 구조체에는 다음과 같이 크게 3가지 종류의 값을 담아야 합니다.
- 재귀 호출의 인자 (단, 참조 형식으로 넘어가는 인자는 제외)
- Stage 변수 포함
- 함수 호출 결과의 반환값을 담는 로컬 변수 (Binary/Nested 타입의 재귀호출에서 나타남)
이 규칙에 따라 FibNum 메서드로부터 각각 값을 대응시켜서,
public static int FibNum(int n)
{
if (n < 1)
{
return -1;
}
if (1 == n || 2 == n)
{
return 1;
}
int addVal = FibNum(n - 1);
addVal += FibNum(n - 2);
return addVal;
}
재귀 호출의 인자: int n;
Stage 변수 포함: int stage;
함수 호출 결과의 반환값을 담는 로컬 변수: int addVal;
반복문으로 피보나치 수열을 구현하는 메서드를 다음과 같이 시작할 수 있습니다.
public struct SnapShotStruct
{
public int n;
public int addVal;
public int stage;
}
public static int FibNumLoop(int n)
{
return 0;
}
만약 원래의 FibNum 메서드가 다음과 같은 형식이었다면 어떻게 SnapShotStruct를 구성해야 할까요?
public static int FibNum(int x, int y, ref int z)
{
...[생략]...
}
인자가 3개지만, z는 ref 형식이기 때문에 x, y만 포함하면 됩니다.
public struct SnapShotStruct
{
public int x, y;
public int addVal;
public int stage;
}
두 번째 단계
반환값으로 사용될 로컬 변수를 가장 상단에 정의해 둡니다. 당연히 원래의 재귀호출 함수가 반환값이 없다면 이 변수는 생략해도 됩니다.
두 번째 단계로 소스코드는 다음과 같이 바뀝니다.
public struct SnapShotStruct
{
public int n;
public int addVal;
public int stage;
}
public static int FibNumLoop(int n)
{
int retVal = 0;
return retVal;
}
세 번째 단계
Snapshot 구조체를 형식인자로 Stack 자료 구조를 하나 만들어 둡니다.
public struct SnapShotStruct
{
public int n;
public int addVal;
public int stage;
}
public static int FibNumLoop(int n)
{
int retVal = 0;
Stack<SnapShotStruct> snapshotStack = new Stack<SnapShotStruct>();
return retVal;
}
네 번째 단계
SnapShotStruct 인스턴스를 하나 만들고, 반복 함수에 전달할 입력값들을 초기화합니다. 만들어둔 SnapShotStruct 인스턴스를 스택에 보관하는 것으로 본격적인 Stage를 시작할 수 있습니다.
public struct SnapShotStruct
{
public int n;
public int addVal;
public int stage;
}
public static int FibNumLoop(int n)
{
int retVal = 0;
Stack<SnapShotStruct> snapshotStack = new Stack<SnapShotStruct>();
SnapShotStruct currentSnapshot = new SnapShotStruct();
currentSnapshot.n = n;
currentSnapshot.addVal = 0;
currentSnapshot.stage = 0;
snapshotStack.Push(currentSnapshot);
return retVal;
}
다섯 번째 단계
재귀호출을 대신할 루프를 만듭니다. 이 루프는 스택을 모두 비울때까지 반복합니다.
public struct SnapShotStruct
{
public int n;
public int addVal;
public int stage;
}
public static int FibNumLoop(int n)
{
int retVal = 0;
Stack<SnapShotStruct> snapshotStack = new Stack<SnapShotStruct>();
SnapShotStruct currentSnapshot = new SnapShotStruct();
currentSnapshot.n = n;
currentSnapshot.addVal = 0;
currentSnapshot.stage = 0;
snapshotStack.Push(currentSnapshot);
while (snapshotStack.Count != 0)
{
currentSnapshot = snapshotStack.Pop();
}
return retVal;
}
여섯 번째 단계
이제부터 실제 재귀 호출 함수의 코드를 반복문 코드로 구획하는 작업에 들어갑니다. 이는 재귀 호출 함수내에서 다시 재귀호출되는 함수의 호출 수에 따라 변합니다.
만약, 1번의 재귀호출만을 포함하는 경우 2단계로 나누면 됩니다. 첫단계는 재귀호출 함수 내에서 다시 재귀호출이 발생하기 까지의 코드를 넣어주고, 두 번째 단계는 그 내부의 재귀호출이 발생한 다음 처리할 코드를 위치시킵니다.
이번 예제에서 든 FibNum 메서드는 내부에 2번의 재귀호출을 포함하므로 3단계로 나뉘어 질 수 있습니다.
- 1단계: FibNum(n - 1) 호출이 있기 전 처리되는 내용을 포함
- 2단계: FibNum(n - 1) 호출이 있은 후, 즉 FibNum(n - 2) 호출이 있기 전 처리되는 내용을 포함
- 3단계: FibNum(n - 2) 호출이 있은 후 처리되는 내용을 포함
(마찬가지로, 만약 재귀 호출 함수 내부에 3번의 재귀 호출이 있다면 4단계로 나뉩니다.)
따라서, FibNum의 경우 다음과 같이 3가지 case 문을 예약합니다.
public struct SnapShotStruct
{
public int n;
public int addVal;
public int stage;
}
public static int FibNumLoop(int n)
{
int retVal = 0;
Stack snapshotStack = new Stack();
SnapShotStruct currentSnapshot = new SnapShotStruct();
currentSnapshot.n = n;
currentSnapshot.addVal = 0;
currentSnapshot.stage = 0;
snapshotStack.Push(currentSnapshot);
while (snapshotStack.Count != 0)
{
currentSnapshot = snapshotStack.Pop();
switch (currentSnapshot.stage)
{
case 0: // before (FibNum(n - 1))
break;
case 1: // after (FibNum(n - 1)) == before (FibNum(n - 2))
break;
case 2: // after (FibNum(n - 2))
break;
}
}
return retVal;
}
일곱 번째 단계
3단계로 나눈 case 문에 이제 적절한 코드를 넣어보겠습니다.
첫 번째 case 문에는 FibNum(n - 1) 호출이 있기 전의 코드를 넣는다고 했으니 다음과 같이 넣어주시면 됩니다.
case 0:
if (n < 1)
{
return -1;
}
if (1 == n || 2 == n)
{
return 1;
}
break;
단지, 여기서 n 값은 SnapShotStruct의 n에 해당합니다.
case 0:
if (currentSnapshot.n < 1)
{
return -1;
}
if (1 == currentSnapshot.n || 2 == currentSnapshot.n)
{
return 1;
}
break;
두 번째 case문의 경우 FibNum(n - 1)의 반환값을 보관하는 코드가 전부이므로 이를 처리합니다.
case 1:
currentSnapshot.addVal = retVal;
break;
마지막으로 세 번째 case는 값을 합산해서 반환한는 코드를 추가합니다.
case 2:
currentSnapshot.addVal = currentSnapshot.addVal + retVal;
return currentSnapshot.addVal;
break;
일곱 번째의 최종 소스 코드는 다음과 같습니다.
public static int FibNumLoop(int n)
{
int retVal = 0;
Stack<SnapShotStruct> snapshotStack = new Stack<SnapShotStruct>();
SnapShotStruct currentSnapshot = new SnapShotStruct();
currentSnapshot.n = n;
currentSnapshot.addVal = 0;
currentSnapshot.stage = 0;
snapshotStack.Push(currentSnapshot);
while (snapshotStack.Count != 0)
{
currentSnapshot = snapshotStack.Pop();
switch (currentSnapshot.stage)
{
case 0:
if (currentSnapshot.n < 1)
{
return -1;
}
if (1 == currentSnapshot.n || 2 == currentSnapshot.n)
{
return 1;
}
break;
case 1:
currentSnapshot.addVal = retVal;
break;
case 2:
currentSnapshot.addVal = currentSnapshot.addVal + retVal;
return currentSnapshot.addVal;
break;
}
}
return retVal;
}
여덟 번째 단계
원본 재귀 함수가 반환 값이 있는 경우, return [value]; 코드를 두 번째 단계에서 마련해 둔 로컬 변수(예제에서는 retVal)에 넣어둡니다. while 루프가 끝났을 때 반복문으로 구현된 우리의 메서드가 반환할 최종값은 retVal에 담겨 있게 됩니다.
이 규칙에 따라 case 0 단계를 다음과 같이 바꿀 수 있고,
case 0:
if (currentSnapshot.n < 1)
{
retVal = -1;
return retVal;
}
if (1 == currentSnapshot.n || 2 == currentSnapshot.n)
{
retVal = 1;
return retVal;
}
break;
두 번째 case 문에는 return 문이 없으므로 생략하고, 세 번째 case문은 다음과 같이 바꿀 수 있습니다.
case 2:
currentSnapshot.addVal = currentSnapshot.addVal + retVal;
retVal = currentSnapshot.addVal;
return retVal;
break;
여덟 번째 규칙까지 반영된 FibNumLoop 메서드 코드입니다.
public static int FibNumLoop(int n)
{
int retVal = 0;
Stack<SnapShotStruct> snapshotStack = new Stack<SnapShotStruct>();
SnapShotStruct currentSnapshot = new SnapShotStruct();
currentSnapshot.n = n;
currentSnapshot.addVal = 0;
currentSnapshot.stage = 0;
snapshotStack.Push(currentSnapshot);
while (snapshotStack.Count != 0)
{
currentSnapshot = snapshotStack.Pop();
switch (currentSnapshot.stage)
{
case 0:
if (currentSnapshot.n < 1)
{
retVal = -1;
return retVal;
}
if (1 == currentSnapshot.n || 2 == currentSnapshot.n)
{
retVal = 1;
return retVal;
}
break;
case 1:
currentSnapshot.addVal = retVal;
break;
case 2:
retVal = currentSnapshot.addVal + retVal;
return retVal;
break;
}
}
return retVal;
}
아홉 번째 단계
재귀함수에 있었던 return 문을 continue로 바꿔줍니다. 사실 아홉 번째 단계는 여덟 번째 단계를 변환하면서 continue로 함께 바꿔주면 되는데, 아마도 (멋있게?) 10단계를 채우기 위해 너무 세세하게 나눈 것이 아닌가 생각됩니다.
암튼, 이에 따라 case 0과 case 2의 "return retVal;" 코드를 단순히 "continue;"로 치환해 주면 됩니다.
public static int FibNumLoop(int n)
{
int retVal = 0;
Stack<SnapShotStruct> snapshotStack = new Stack<SnapShotStruct>();
SnapShotStruct currentSnapshot = new SnapShotStruct();
currentSnapshot.n = n;
currentSnapshot.addVal = 0;
currentSnapshot.stage = 0;
snapshotStack.Push(currentSnapshot);
while (snapshotStack.Count != 0)
{
currentSnapshot = snapshotStack.Pop();
switch (currentSnapshot.stage)
{
case 0:
if (currentSnapshot.n < 1)
{
retVal = -1;
continue;
}
if (1 == currentSnapshot.n || 2 == currentSnapshot.n)
{
retVal = 1;
continue;
}
break;
case 1:
currentSnapshot.addVal = retVal;
break;
case 2:
retVal = currentSnapshot.addVal + retVal;
continue;
}
}
return retVal;
}
열 번째 단계
마지막으로 가장 중요한 단계입니다. 원본 재귀 호출 함수 내에서 실제로 재귀 호출이 되는 부분을 반복문으로 바꾸기 위해 재귀 호출 하나 당 SnapShotStruct 객체로 만들어 줍니다.
이와 함께 현재 case의 SnapShotStruct 인스턴스가 다음번 case 문으로 진행할 수 있도록 stage 값을 증가시키고, 다시 Stack 목록에 추가시킵니다. (Stack 목록에 추가시키지 않으면 while 문에서 처리가 안될테니까요.)
FibNum(n - 1) 호출을 case 0번에 심어보면 다음과 같습니다.
case 0:
if (currentSnapshot.n < 1)
{
retVal = -1;
continue;
}
if (1 == currentSnapshot.n || 2 == currentSnapshot.n)
{
retVal = 1;
continue;
}
SnapShotStruct newSnapShotN1 = new SnapShotStruct();
newSnapShotN1.n = currentSnapshot.n - 1;
newSnapShotN1.addVal = 0;
newSnapShotN1.stage = 0;
snapshotStack.Push(newSnapShotN1);
break;
보시는 바와 같이 새로운 SnapShotStruct 인스턴스를 생성해 stage = 0으로 처리함으로써 다음번 while 문에서 case 0부터 처리가 시작되도록 만들어 주었습니다.
아울러, case 0에 이미 진입한 현재의 SnapShotStruct 인스턴스 자체는 다음 case 문으로 진행할 수 있도록 stage를 증가시키고 다시 Stack 목록에 추가해 둡니다.
case 0:
if (currentSnapshot.n < 1)
{
retVal = -1;
continue;
}
if (1 == currentSnapshot.n || 2 == currentSnapshot.n)
{
retVal = 1;
continue;
}
currentSnapshot.stage = 1;
snapshotStack.Push(currentSnapshot);
SnapShotStruct newSnapShotN1 = new SnapShotStruct();
newSnapShotN1.n = currentSnapshot.n - 1;
newSnapShotN1.addVal = 0;
newSnapShotN1.stage = 0;
snapshotStack.Push(newSnapShotN1);
break;
그다음, FibNum(n - 2) 호출도 처리해보겠습니다. 이건 case 0이 아니라 case 1에서 처리해야 합니다.
case 1:
currentSnapshot.addVal = retVal;
SnapShotStruct newSnapShotN2 = new SnapShotStruct();
newSnapShotN2.n = currentSnapshot.n - 2;
newSnapShotN2.addVal = 0;
newSnapShotN2.stage = 0;
snapshotStack.Push(newSnapShotN2);
break;
새로 추가된 newSnapShotN2는 당연히 stage 0부터 시작해야 합니다. 마찬가지로 case 1까지 진입한 SnapShotStruct 인스턴스도 다음번 while 처리에서 case 2로 진행할 수 있도록 stage를 증가시킵니다.
case 1:
currentSnapshot.addVal = retVal;
currentSnapshot.stage = 2;
snapshotStack.Push(currentSnapshot);
SnapShotStruct newSnapShotN2 = new SnapShotStruct();
newSnapShotN2.n = currentSnapshot.n - 2;
newSnapShotN2.addVal = 0;
newSnapShotN2.stage = 0;
snapshotStack.Push(newSnapShotN2);
break;
case 2에서는 재귀 호출이 없으므로 할 일이 없습니다. 이렇게 해서 모든 변환이 끝난 최종 메서드는 다음과 같이 구현이 완료됩니다.
public static int FibNumLoop(int n)
{
int retVal = 0;
Stack<SnapShotStruct> snapshotStack = new Stack<SnapShotStruct>();
SnapShotStruct currentSnapshot = new SnapShotStruct();
currentSnapshot.n = n;
currentSnapshot.addVal = 0;
currentSnapshot.stage = 0;
snapshotStack.Push(currentSnapshot);
while (snapshotStack.Count != 0)
{
currentSnapshot = snapshotStack.Pop();
switch (currentSnapshot.stage)
{
case 0:
if (currentSnapshot.n < 1)
{
retVal = -1;
continue;
}
if (1 == currentSnapshot.n || 2 == currentSnapshot.n)
{
retVal = 1;
continue;
}
currentSnapshot.stage = 1;
snapshotStack.Push(currentSnapshot);
SnapShotStruct newSnapShotN1 = new SnapShotStruct();
newSnapShotN1.n = currentSnapshot.n - 1;
newSnapShotN1.addVal = 0;
newSnapShotN1.stage = 0;
snapshotStack.Push(newSnapShotN1);
break;
case 1:
currentSnapshot.addVal = retVal;
currentSnapshot.stage = 2;
snapshotStack.Push(currentSnapshot);
SnapShotStruct newSnapShotN2 = new SnapShotStruct();
newSnapShotN2.n = currentSnapshot.n - 2;
newSnapShotN2.addVal = 0;
newSnapShotN2.stage = 0;
snapshotStack.Push(newSnapShotN2);
break;
case 2:
retVal = currentSnapshot.addVal + retVal;
continue;
}
}
return retVal;
}
초보 프로그래머의 경우 재귀 호출의 특수성으로 잘 이해가 안되는 경우가 있을텐데요. 사실 위에서 보는 것처럼 재귀호출은 무척 쉬운 문제 해결 방법입니다. 재귀 호출로 구현된 코드를 일반 메서드 방식으로 변경한 경우 저렇게 소스 코드가 길어지는데다 이해하는 것도 더 어려워지고 실수도 발생할 확률이 높아지기 때문입니다.
경우에 따라서는 일반 메서드 호출이 더 어렵답니다. ^^
(
첨부 파일은 위의 예제 코드를 포함합니다.)
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]