Page 176 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

니다. 다음은 스택을 사용하여 비재귀적으로 구현한 recur 함수입니다.

이 프로그램의 컴파일, 실행에는 실습 4-1의 IntStack.h와 실습 4-2의 IntStack.c가 필요합니다.

실습 5-5 •완성 파일 chap05/recur_nr2.c
01 /*--- 재귀 호출을 제거한 recur 함수 ---*/
02 void recur(int n)
03 {
04 IntStack stk; /* 스택 */
05 Initialize(&stk, 100);
06 Top :
07 if(n > 0) {
08 1 Push(&stk, n); /* n의 값을 푸시 */
09 2 n = n - 1;
10 3 goto Top;
11 }
12 if(!IsEmpty(&stk)) { /* 스택이 비어 있지 않으면 */
13 4 Pop(&stk, &n); /* 값을 저장했던 n을 팝 */
14 5 printf("%d\n", n);
15 6 n = n - 2;
16 7 goto Top;
17 }
18
19 Terminate(&stk);
20 }

recur(4)를 호출한 다음의 과정을 살펴보겠습니다. 매개변수로 전달받은 값 ‘4’는 0보다 크므

로 맨 앞의 if문에 의해 다음과 같은 과정이 진행됩니다.

1 4를 스택에 푸시합니다(그림 5-7 a ).
2 n의 값을 하나 줄여 3으로 만듭니다.
3 goto문이 실행되어 레이블(Label) Top으로 돌아갑니다.

3은 0보다 크므로 첫 번째 if문이 실행됩니다. 그 결과 위의 과정이 반복됩니다. 그러면 그림 b
⇨ 그림 c ⇨ 그림 d 의 순서대로 실행되면서 스택에 4, 3, 2, 1이 쌓이게 됩니다. 마지막으로
스택에 1을 쌓은 뒤 0이 되고 Top으로 돌아가서 맨 앞 if문이 실행됩니다. 그러면 n 값이 0이므

로 첫 번째 if문은 그냥 지나가고 다음의 if문에 의해 다음과 같은 과정이 진행됩니다.

176 C 알고리즘