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

갑니다.

조금만 더! recur(3)의 호출에 대해 더 자세히 알아볼까요?

예를 들어 recur(3)을 호출하면 그림 5-5 왼쪽 아래 상자의 recur(0)까지는 계속 왼쪽 화살표를 따라 가
기 때문에 ‘4’를 바로 출력할 수 없습니다. recur(0)의 왼쪽 화살표에서 빈 상자를 만나 recur(0)을 호
출한 상자로 돌아가 ‘1’을 출력하고, 이어 일련의 작업 중 하나인 recur(-1)을 호출해 다시 빈 상자를 만
나서 돌아오면 비로소 recur(0)을 호출한 상자에서 한 칸 위의 상자로 돌아갑니다. 차근차근 생각해보면
recur(3)을 호출한 상자로 돌아가기 위해 많은 단계를 거쳐야 함을 알 수 있습니다.

이처럼 가장 위쪽에 위치한 상자의 함수 호출부터 시작해 계단식으로 자세히 조사해 가는 분
석 기법을 하향식 분석(top-down analysis)이라고 합니다. 그런데 이 그림 안에는 recur(1),
recur(2)의 호출이 여러 번 있습니다(같은 호출이 여러 번 있습니다). 꼭대기(top)부터 분석하면
이렇게 같은 함수의 호출이 여러 번 나올 수 있기 때문에 ‘하향식 분석이 반드시 효율적이다’

라고 말할 수는 없습니다.

상향식 분석

위쪽부터 분석하는 하향식 분석과는 대조적으로 아래쪽부터 쌓아 올리며 분석하는 방법이
상향식 분석(bottom-up analysis)입니다. recur 함수는 n이 양수일 때만 실행하므로 먼저
recur(1)을 생각합니다. recur(1)이 수행하는 작업은 아래와 같습니다.

① recur(0)을 실행합니다.
② 1을 출력합니다.
③ recur(-1)을 실행합니다.

여기서 ①의 recur(0)과 ③의 recur(-1)은 출력할 내용이 없습니다. 따라서 ②의 1만 출력합

니다. 그럼 recur(2)에 대해 생각해 봅시다.

① recur(1)을 실행합니다.
② 2를 출력합니다.
③ recur(0)을 실행합니다.

①의 recur(1)은 1을 출력하고 ③의 recur(0)은 출력할 내용이 없습니다. 전체 과정을 거치면

05•재귀 알고리즘 173