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

recur 함수는 factorial 함수나 gcd 함수와 달리 함수 안에서 재귀 호출을 2회 실행합니다. 이

처럼 재귀 호출을 여러 회 실행하는 함수를 순수하게(genuinely) 재귀적이라 하는데 실제 동
작은 매우 복잡합니다. 실습 5-3의 recur 함수에 매개변수로 4를 전달하면 ‘1231412’라고
숫자를 한 줄에 한 글자씩 출력하는데, 이런 복잡한 구조를 가진 재귀 함수는 좀 더 전략적으
로 분석해야 합니다. 여기서는 recur 함수를 하향식과 상향식의 두 방법으로 분석합니다.

하향식 분석
매개변수 n으로 4를 전달하면 recur 함수는 아래 과정을 순서대로 실행합니다.

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

물론 ②에서 4를 출력하는 것은 ①의 recur(3)의 실행이 완료된 다음입니다. 따라서 recur(3)

을 먼저 조사해야 합니다. 말로 설명하는 것은 어렵기 때문에 아래의 그림 5-5를 예로 들어
설명하겠습니다. 각각의 상자는 recur 함수의 동작을 나타냅니다. 또 전달받은 값이 0 이하면
recur 함수는 아무 일도 하지 않으므로 빈 상자로 표시됩니다(상자 안에 ‘-’를 표기).

recur(3);  recur(2);

recur(2);  recur(1); recur(1);  recur(0);

recur(1);  recur(0); recur(0);  recur(-1); recur(0);  recur(-1); －

recur(0);  recur(-1); － － － － －

－ － 1. 왼쪽 아래로 화살표를 따라 갑니다.
2. 되돌아오면 ■ 안의 값을 출력합니다.
3 오른쪽 아래로 화살표를 따라 갑니다.

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

①의 recur(3)의 호출 이후에 어떤 과정을 거치게 되는지는 왼쪽 화살표를 따라 가면 됩니다.
위 그림을 읽는 방법에 대해 설명하겠습니다. ‘왼쪽 화살표를 따라 하나 아래 상자로 이동하
고, 다시 원래의 상자로 돌아오면 ■ 안의 값을 출력하고 이어서 오른쪽 화살표를 따라 한 칸

아래 상자로 이동한다’를 일련의 작업으로 생각합니다. 이렇게 하나의 작업이 완료되어야 한
칸 위의 상자로 돌아갈 수 있습니다. 물론 빈 상자에 도달하는 경우 아무것도 하지 않고 돌아

172 C 알고리즘