성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
MathJax 입력기
최근 덧글
[정성태] Working with Rust Libraries from C#...
[정성태] Detecting blocking calls using asyn...
[정성태] 아쉽게도, 커뮤니티는 아니고 개인 블로그입니다. ^^
[정성태] 질문이 잘 이해가 안 됩니다. 우선, 해당 소스코드에서 ILis...
[양승조
] var대신 dinamic으로 선언해서 해결은 했습니다. 맞는 해...
[양승조
] 또 막혔습니다. ㅠㅠ var list = props[i].Ge...
[양승조
] 아. 감사합니다. 어제는 안됐던것 같은데....정신을 차려야겠네...
[정성태] "props[i].GetValue(props[i])" 코드에서 ...
[정성태] 저렇게 조각 코드 말고, 실제로 재현이 되는 예제 프로젝트를 압...
[정성태] Modules 창(Ctrl+Shift+U)을 띄워서, 해당 Op...
글쓰기
제목
이름
암호
전자우편
HTML
홈페이지
유형
제니퍼 .NET
닷넷
COM 개체 관련
스크립트
VC++
VS.NET IDE
Windows
Team Foundation Server
디버깅 기술
오류 유형
개발 환경 구성
웹
기타
Linux
Java
DDK
Math
Phone
Graphics
사물인터넷
부모글 보이기/감추기
내용
<div style='display: inline'> <h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>C# - 재귀호출을 스택 자료구조와 반복문을 이용해 대체하는 방법</h1> <p> 미리 말씀드리지만 이 글은 다음의 글을 제맘대로 번역한 것입니다. (번역이라고 말하기 좀 그렇군요. 그냥 그 글을 기반으로 썼다고 하는 편이 맞겠지요. ^^)<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > How to replace recursive functions using stack and while-loop to avoid the stack-overflow ; <a target='tab' href='http://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and'>http://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and</a> </pre> <br /> 사실 자료구조 공부를 좀 하신 분은 위의 글이 말하는 내용에 대해 이미 알고 계실 텐데요. 그래도 코드와 함께 이해하기 쉽게 글이 쓰여졌기 때문에 공유 차원에서 번역해 봅니다. ^^<br /> <br /> <hr style='width: 50%' /><br /> <br /> 재귀호출은 잘 쓰면 로직이 깔끔해지지만, 한 가지 단점이라면 깊이가 증가하는 경우 stack-overflow 예외가 발생할 수 있습니다. (윈도우 프로그램의 경우 기본 스레드 스택 크기는 1MB입니다.) <br /> <br /> 물론 스레드 스택 크기를 늘림으로써 경우에 따라 스택오버플로우 예외를 빗겨갈 수는 있지만 근본적인 해결책은 되지 않습니다. 따라서, 재귀호출을 반복문으로 변환할 줄 아는 것이 도움이 될 수 있는데요.<br /> <br /> 이제부터 재귀호출로 작성된 피보나치 수열 메서드를 10단계의 작업을 거쳐 반복문으로 바꾸는 방법을 소개할텐데, "<a target='tab' href='http://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and'>How to replace recursive functions using stack and while-loop to avoid the stack-overflow</a>" 원문의 경우 C/C++ 언어로 했지만 이 글에서는 C#으로 합니다.<br /> <br /> 즉, 재귀호출로 작성된 다음의 코드를 10단계로 나눠 반복문으로 바꿀 것입니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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; } } } </pre> <br /> 참고로, 재귀호출은 유형별로 Linear, Tail, Binary, Nested로 나뉘는데 이 글의 예제로 사용되는 FibNum 메서드는 Binary Recursion에 해당합니다. 그 외 자세한 사항은 다음의 글을 참고하세요. ^^<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Type of Recursion ; <a target='tab' href='http://proneer.tistory.com/231'>http://proneer.tistory.com/231</a> </pre> <br /> 그럼, 한 단계씩 따라가 볼까요? ^^<br /> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>첫 번째 단계</div> <br /> 재귀 호출 메서드에서 사용되는 값의 상태를 보관하는 용도로 "Snapshot" 구조체를 하나 만듭니다. 이 구조체에는 다음과 같이 크게 3가지 종류의 값을 담아야 합니다.<br /> <br /> <ul> <li>재귀 호출의 인자 (단, 참조 형식으로 넘어가는 인자는 제외)</li> <li>Stage 변수 포함</li> <li>함수 호출 결과의 반환값을 담는 로컬 변수 (Binary/Nested 타입의 재귀호출에서 나타남)</li> </ul> <br /> 이 규칙에 따라 FibNum 메서드로부터 각각 값을 대응시켜서,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > public static int FibNum(<span style='color: blue; font-weight: bold'>int n</span>) { if (n < 1) { return -1; } if (1 == n || 2 == n) { return 1; } <span style='color: blue; font-weight: bold'>int addVal</span> = FibNum(n - 1); addVal += FibNum(n - 2); return addVal; } 재귀 호출의 인자: int n; Stage 변수 포함: int stage; 함수 호출 결과의 반환값을 담는 로컬 변수: int addVal; </pre> <br /> 반복문으로 피보나치 수열을 구현하는 메서드를 다음과 같이 시작할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > public struct SnapShotStruct { public int n; public int addVal; public int stage; } public static int FibNumLoop(int n) { return 0; } </pre> <br /> 만약 원래의 FibNum 메서드가 다음과 같은 형식이었다면 어떻게 SnapShotStruct를 구성해야 할까요?<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > public static int FibNum(<span style='color: blue; font-weight: bold'>int x, int y, ref int z</span>) { ...[생략]... } </pre> <br /> 인자가 3개지만, z는 ref 형식이기 때문에 x, y만 포함하면 됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > public struct SnapShotStruct { <span style='color: blue; font-weight: bold'>public int x, y;</span> public int addVal; public int stage; } </pre> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>두 번째 단계</div> <br /> 반환값으로 사용될 로컬 변수를 가장 상단에 정의해 둡니다. 당연히 원래의 재귀호출 함수가 반환값이 없다면 이 변수는 생략해도 됩니다.<br /> <br /> 두 번째 단계로 소스코드는 다음과 같이 바뀝니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > public struct SnapShotStruct { public int n; public int addVal; public int stage; } public static int FibNumLoop(int n) { <span style='color: blue; font-weight: bold'>int retVal = 0;</span> return retVal; } </pre> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>세 번째 단계</div> <br /> Snapshot 구조체를 형식인자로 Stack 자료 구조를 하나 만들어 둡니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > public struct SnapShotStruct { public int n; public int addVal; public int stage; } public static int FibNumLoop(int n) { int retVal = 0; <span style='color: blue; font-weight: bold'>Stack<SnapShotStruct> snapshotStack = new Stack<SnapShotStruct>();</span> return retVal; } </pre> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>네 번째 단계</div> <br /> SnapShotStruct 인스턴스를 하나 만들고, 반복 함수에 전달할 입력값들을 초기화합니다. 만들어둔 SnapShotStruct 인스턴스를 스택에 보관하는 것으로 본격적인 Stage를 시작할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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>(); <span style='color: blue; font-weight: bold'> SnapShotStruct currentSnapshot = new SnapShotStruct(); currentSnapshot.n = n; currentSnapshot.addVal = 0; currentSnapshot.stage = 0; snapshotStack.Push(currentSnapshot);</span> return retVal; } </pre> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>다섯 번째 단계</div> <br /> 재귀호출을 대신할 루프를 만듭니다. 이 루프는 스택을 모두 비울때까지 반복합니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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); <span style='color: blue; font-weight: bold'> while (snapshotStack.Count != 0) { currentSnapshot = snapshotStack.Pop(); }</span> return retVal; } </pre> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>여섯 번째 단계</div> <br /> 이제부터 실제 재귀 호출 함수의 코드를 반복문 코드로 구획하는 작업에 들어갑니다. 이는 재귀 호출 함수내에서 다시 재귀호출되는 함수의 호출 수에 따라 변합니다.<br /> <br /> 만약, 1번의 재귀호출만을 포함하는 경우 2단계로 나누면 됩니다. 첫단계는 재귀호출 함수 내에서 다시 재귀호출이 발생하기 까지의 코드를 넣어주고, 두 번째 단계는 그 내부의 재귀호출이 발생한 다음 처리할 코드를 위치시킵니다.<br /> <br /> 이번 예제에서 든 FibNum 메서드는 내부에 2번의 재귀호출을 포함하므로 3단계로 나뉘어 질 수 있습니다.<br /> <br /> <ul> <li>1단계: FibNum(n - 1) 호출이 있기 전 처리되는 내용을 포함</li> <li>2단계: FibNum(n - 1) 호출이 있은 후, 즉 FibNum(n - 2) 호출이 있기 전 처리되는 내용을 포함</li> <li>3단계: FibNum(n - 2) 호출이 있은 후 처리되는 내용을 포함</li> </ul> <br /> (마찬가지로, 만약 재귀 호출 함수 내부에 3번의 재귀 호출이 있다면 4단계로 나뉩니다.)<br /> <br /> 따라서, FibNum의 경우 다음과 같이 3가지 case 문을 예약합니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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(); <span style='color: blue; font-weight: bold'> 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; }</span> } return retVal; } </pre> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>일곱 번째 단계</div> <br /> 3단계로 나눈 case 문에 이제 적절한 코드를 넣어보겠습니다.<br /> <br /> 첫 번째 case 문에는 FibNum(n - 1) 호출이 있기 전의 코드를 넣는다고 했으니 다음과 같이 넣어주시면 됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > case 0: if (n < 1) { return -1; } if (1 == n || 2 == n) { return 1; } break; </pre> <br /> 단지, 여기서 n 값은 SnapShotStruct의 n에 해당합니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > case 0: if (currentSnapshot.n < 1) { return -1; } if (1 == currentSnapshot.n || 2 == currentSnapshot.n) { return 1; } break; </pre> <br /> 두 번째 case문의 경우 FibNum(n - 1)의 반환값을 보관하는 코드가 전부이므로 이를 처리합니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > case 1: currentSnapshot.addVal = retVal; break; </pre> <br /> 마지막으로 세 번째 case는 값을 합산해서 반환한는 코드를 추가합니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > case 2: currentSnapshot.addVal = currentSnapshot.addVal + retVal; return currentSnapshot.addVal; break; </pre> <br /> 일곱 번째의 최종 소스 코드는 다음과 같습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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: <span style='color: blue; font-weight: bold'> if (currentSnapshot.n < 1) { return -1; } if (1 == currentSnapshot.n || 2 == currentSnapshot.n) { return 1; }</span> break; case 1: <span style='color: blue; font-weight: bold'> currentSnapshot.addVal = retVal;</span> break; case 2: <span style='color: blue; font-weight: bold'> currentSnapshot.addVal = currentSnapshot.addVal + retVal; return currentSnapshot.addVal;</span> break; } } return retVal; } </pre> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>여덟 번째 단계</div> <br /> 원본 재귀 함수가 반환 값이 있는 경우, return [value]; 코드를 두 번째 단계에서 마련해 둔 로컬 변수(예제에서는 retVal)에 넣어둡니다. while 루프가 끝났을 때 반복문으로 구현된 우리의 메서드가 반환할 최종값은 retVal에 담겨 있게 됩니다.<br /> <br /> 이 규칙에 따라 case 0 단계를 다음과 같이 바꿀 수 있고,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > case 0: if (currentSnapshot.n < 1) { <span style='color: blue; font-weight: bold'> retVal = -1; return retVal;</span> } if (1 == currentSnapshot.n || 2 == currentSnapshot.n) { <span style='color: blue; font-weight: bold'> retVal = 1; return retVal;</span> } break; </pre> <br /> 두 번째 case 문에는 return 문이 없으므로 생략하고, 세 번째 case문은 다음과 같이 바꿀 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > case 2: currentSnapshot.addVal = currentSnapshot.addVal + retVal; <span style='color: blue; font-weight: bold'> retVal = currentSnapshot.addVal; return retVal;</span> break; </pre> <br /> 여덟 번째 규칙까지 반영된 FibNumLoop 메서드 코드입니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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) { <span style='color: blue; font-weight: bold'> retVal = -1; return retVal;</span> } if (1 == currentSnapshot.n || 2 == currentSnapshot.n) { <span style='color: blue; font-weight: bold'> retVal = 1; return retVal;</span> } break; case 1: currentSnapshot.addVal = retVal; break; case 2: <span style='color: blue; font-weight: bold'> retVal = currentSnapshot.addVal + retVal; return retVal;</span> break; } } return retVal; } </pre> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>아홉 번째 단계</div> <br /> 재귀함수에 있었던 return 문을 continue로 바꿔줍니다. 사실 아홉 번째 단계는 여덟 번째 단계를 변환하면서 continue로 함께 바꿔주면 되는데, 아마도 (멋있게?) 10단계를 채우기 위해 너무 세세하게 나눈 것이 아닌가 생각됩니다.<br /> <br /> 암튼, 이에 따라 case 0과 case 2의 "return retVal;" 코드를 단순히 "continue;"로 치환해 주면 됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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; <span style='color: blue; font-weight: bold'>continue;</span> } if (1 == currentSnapshot.n || 2 == currentSnapshot.n) { retVal = 1; <span style='color: blue; font-weight: bold'>continue;</span> } break; case 1: currentSnapshot.addVal = retVal; break; case 2: retVal = currentSnapshot.addVal + retVal; <span style='color: blue; font-weight: bold'>continue;</span> } } return retVal; } </pre> <br /> <br /><div style='font-size: 12pt; font-family: Malgun Gothic, Consolas; color: #2211AA; text-align: left; font-weight: bold'>열 번째 단계</div> <br /> 마지막으로 가장 중요한 단계입니다. 원본 재귀 호출 함수 내에서 실제로 재귀 호출이 되는 부분을 반복문으로 바꾸기 위해 재귀 호출 하나 당 SnapShotStruct 객체로 만들어 줍니다. <br /> <br /> 이와 함께 현재 case의 SnapShotStruct 인스턴스가 다음번 case 문으로 진행할 수 있도록 stage 값을 증가시키고, 다시 Stack 목록에 추가시킵니다. (Stack 목록에 추가시키지 않으면 while 문에서 처리가 안될테니까요.)<br /> <br /> FibNum(n - 1) 호출을 case 0번에 심어보면 다음과 같습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > case 0: if (currentSnapshot.n < 1) { retVal = -1; continue; } if (1 == currentSnapshot.n || 2 == currentSnapshot.n) { retVal = 1; continue; } <span style='color: blue; font-weight: bold'> SnapShotStruct newSnapShotN1 = new SnapShotStruct(); newSnapShotN1.n = currentSnapshot.n - 1; newSnapShotN1.addVal = 0; newSnapShotN1.stage = 0; snapshotStack.Push(newSnapShotN1);</span> break; </pre> <br /> 보시는 바와 같이 새로운 SnapShotStruct 인스턴스를 생성해 stage = 0으로 처리함으로써 다음번 while 문에서 case 0부터 처리가 시작되도록 만들어 주었습니다.<br /> <br /> 아울러, case 0에 이미 진입한 현재의 SnapShotStruct 인스턴스 자체는 다음 case 문으로 진행할 수 있도록 stage를 증가시키고 다시 Stack 목록에 추가해 둡니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > case 0: if (currentSnapshot.n < 1) { retVal = -1; continue; } if (1 == currentSnapshot.n || 2 == currentSnapshot.n) { retVal = 1; continue; } <span style='color: blue; font-weight: bold'> currentSnapshot.stage = 1; snapshotStack.Push(currentSnapshot);</span> SnapShotStruct newSnapShotN1 = new SnapShotStruct(); newSnapShotN1.n = currentSnapshot.n - 1; newSnapShotN1.addVal = 0; newSnapShotN1.stage = 0; snapshotStack.Push(newSnapShotN1); break; </pre> <br /> 그다음, FibNum(n - 2) 호출도 처리해보겠습니다. 이건 case 0이 아니라 case 1에서 처리해야 합니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > case 1: currentSnapshot.addVal = retVal; <span style='color: blue; font-weight: bold'> SnapShotStruct newSnapShotN2 = new SnapShotStruct(); newSnapShotN2.n = currentSnapshot.n - 2; newSnapShotN2.addVal = 0; newSnapShotN2.stage = 0; snapshotStack.Push(newSnapShotN2);</span> break; </pre> <br /> 새로 추가된 newSnapShotN2는 당연히 stage 0부터 시작해야 합니다. 마찬가지로 case 1까지 진입한 SnapShotStruct 인스턴스도 다음번 while 처리에서 case 2로 진행할 수 있도록 stage를 증가시킵니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > case 1: currentSnapshot.addVal = retVal; <span style='color: blue; font-weight: bold'> currentSnapshot.stage = 2; snapshotStack.Push(currentSnapshot);</span> SnapShotStruct newSnapShotN2 = new SnapShotStruct(); newSnapShotN2.n = currentSnapshot.n - 2; newSnapShotN2.addVal = 0; newSnapShotN2.stage = 0; snapshotStack.Push(newSnapShotN2); break; </pre> <br /> case 2에서는 재귀 호출이 없으므로 할 일이 없습니다. 이렇게 해서 모든 변환이 끝난 최종 메서드는 다음과 같이 구현이 완료됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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; } <span style='color: blue; font-weight: bold'> currentSnapshot.stage = 1; snapshotStack.Push(currentSnapshot); SnapShotStruct newSnapShotN1 = new SnapShotStruct(); newSnapShotN1.n = currentSnapshot.n - 1; newSnapShotN1.addVal = 0; newSnapShotN1.stage = 0; snapshotStack.Push(newSnapShotN1);</span> break; case 1: currentSnapshot.addVal = retVal; <span style='color: blue; font-weight: bold'> currentSnapshot.stage = 2; snapshotStack.Push(currentSnapshot); SnapShotStruct newSnapShotN2 = new SnapShotStruct(); newSnapShotN2.n = currentSnapshot.n - 2; newSnapShotN2.addVal = 0; newSnapShotN2.stage = 0; snapshotStack.Push(newSnapShotN2);</span> break; case 2: retVal = currentSnapshot.addVal + retVal; continue; } } return retVal; } </pre> <br /> 초보 프로그래머의 경우 재귀 호출의 특수성으로 잘 이해가 안되는 경우가 있을텐데요. 사실 위에서 보는 것처럼 재귀호출은 무척 쉬운 문제 해결 방법입니다. 재귀 호출로 구현된 코드를 일반 메서드 방식으로 변경한 경우 저렇게 소스 코드가 길어지는데다 이해하는 것도 더 어려워지고 실수도 발생할 확률이 높아지기 때문입니다.<br /> <br /> 경우에 따라서는 일반 메서드 호출이 더 어렵답니다. ^^<br /> <br /> (<a target='tab' href='http://www.sysnet.pe.kr/bbs/DownloadAttachment.aspx?fid=818&boardid=331301885'>첨부 파일은 위의 예제 코드를 포함</a>합니다.)<br /> </p><br /> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
2152
(왼쪽의 숫자를 입력해야 합니다.)