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

1과 2를 출력합니다. 이 작업을 recur(4)까지 쌓아 올려 설명한 내용이 그림 5-6입니다. 다음

과 같은 과정을 거치면 recur(4)가 출력됩니다.

recur(-1) ： 아무것도 하지 않음
recur(0) ： 아무것도 하지 않음

recur(1) ： recur(0)  recur(-1) ⇨ 
recur(2) ： recur(1)  recur(0) ⇨ 
recur(3) ： recur(2)  recur(1) ⇨ 
recur(4) ： recur(3)  recur(2) ⇨ 

[그림 5-6] recur 함수의 상향식 분석

Q4 오른쪽의 recur2 함수를 보고 하향식 분석과 상향식 분석을
연습 void recur2(int n)
문제 수행해 보세요. {
if(n > 0) {
recur2(n - 2);
printf("%d\n", n);
recur2(n - 1);
}
}

재귀 알고리즘의 비재귀적 표현

recur 함수를 재귀 호출을 사용하지 않고 구현하는 방법에 대해 살펴보겠습니다.

꼬리 재귀의 제거
함수의 꼬리에서 재귀 호출하는 함수 recur(n – 2)라는 말은 ‘인자로 n – 2를 전달하여 recur

함수를 호출한다’는 의미입니다. 따라서 이 호출은 아래처럼 바꿀 수 있습니다.

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

실습 5-4는 이 방법을 그대로 구현한 프로그램입니다. recur 함수는 n의 값을 –2만큼 줄인
다음 goto문을 사용해 함수의 시작 지점으로 돌아갑니다.

goto문은 본문의 설명을 코드로 간단하게 표현하기 위해 사용한 문법입니다.

174 C 알고리즘