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

실습 5-4 •완성 파일 chap05/recur_nr1.c
01 /*--- 함수 recur(꼬리 재귀를 제거) ---*/
02 void recur(int n)
03 {
04 Top :
05 if(n > 0) {
06 recur(n - 1);
07 printf("%d\n", n);
08 n = n - 2;
09 goto Top;
10 }
11 }

이렇게 하면 함수의 끝에서 실행하는 꼬리 재귀(tail recursion)는 쉽게 제거할 수 있습니다.

재귀의 제거
그런데 꼬리 재귀와는 다르게 앞에서 호출한 재귀 함수의 제거는 쉽지 않습니다. 왜냐하면 변

수 n의 값을 출력하기 전에 recur(n – 1)을 먼저 수행해야 하기 때문입니다. 예를 들어, n이
4인 경우 재귀 호출 recur(3)의 처리가 완료되지 않으면 n의 값인 ‘4’를 저장해야 합니다. 그
래서 재귀 호출 recur(n – 1)을 아래처럼 바로 바꿀 수 없습니다.

n의 값을 n – 1로 업데이트하고 함수의 시작 지점으로 돌아갑니다.

왜냐하면 다음과 같은 처리를 미리 해야 하기 때문입니다.

현재 n의 값을 ‘잠시’ 저장합니다.

또 recur(n – 1)의 처리가 완료된 다음에 n의 값을 출력할 때는 다음 과정을 따르게 됩니다.

저장했던 n을 다시 꺼내 그 값을 출력합니다.

이런 재귀 호출을 제거하기 위해서는 변수 n의 값을 ‘잠시’ 저장해야 한다는 사실을 알았습니

다. 이때 이런 문제를 잘 해결할 수 있는 데이터 구조가 바로 앞 장에서 살펴본 스택(stack)입

05•재귀 알고리즘 175