[Java] 자바로 프로그래밍 입문하기: 2.3. 재귀 (2)

 그레이 부호(Gray codes)

  하노이의 탑 문제는 단순히 재귀를 설명하기 위해서 만든 문제가 아닙니다. 숫자나 개별 물체들을 생성하는데 아주 밀접한 관계를 가지고 있죠. 그레이 부호를 알아봅시다.

  극작가 사뮈엘 베케트는, <고도를 기다리며>로 유명한 극작가입니다. <쿼드>라는 희곡은 재미있는 특성이 있는데요. 빈 무대에서 시작해 등장 인물들이 입장하고 퇴장합니다. 이 때 단 한 명만 입장하거나, 퇴장합니다. 이런 규칙을 통해서, 무대 위에 있는 등장 인물들이 이룰 수 있는 모든 조합이 단 한 번씩만 나타나게 구성되어 있죠. 베케트는 어떻게 이런 구성을 만들 수 있었을까요? 다음 그림을 참고해보세요.

  n개의 각기 다른 요소들의 부분집합을 표현하는 방법 중 하나는, n개의 비트를 이용하는 것입니다. 베케트의 문제에서, 값이 1이면 무대에 있음을 의미하는 4-비트열을 이용해 문제를 해결해볼 수 있습니다. 우측부터 첫번째 등장 인물이며, 예를 들어 0101이면 첫번째 등장 인물과 세번째 등장인물이 무대에 올라서 있음을 의미합니다. 이 표현법을 통해 다음 사실을 증명할 수 있는데요. 원소의 개수가 n개인 집합의 부분집합은 2^n개라는 사실입니다. <쿼드>는 4명의 등장 인물들이 등장하므로, 16개의 장면들이 존재함을 알 수 있죠.

  n-비트 그레이 부호는 2^n개로 이루어진 서로 다른 n-비트 이진수 목록입니다. 아주 중요한 특징이 있는데, 연속된 수가 단 하나의 비트만 다르다는 점입니다. 베케트의 문제와 그레이 부호는 동일하죠. 단 한 명의 등장인물이 입장하거나 퇴장하는 것은, 곧 그레이 부호에서 비트 하나만 바뀌는 것과 동일한 개념이기 때문입니다.

  어떻게 그레이 부호를 생성해낼 수 있을까요? 하노이의 탑에서 우리가 사용했던 것처럼, 재귀적인 방법을 통해서 아주 효과적으로 이 문제를 해결할 수 있습니다. n-비트 이진수로 표현된 그레이 부호는 재귀적으로 다음과 같이 정의될 수 있습니다.

• (n-1)비트 부호 앞에 0을 전부 붙인 것과,
• (n-1)비트 부호 앞에 1을 전부 붙인 것을 역순으로 표현한 것의 집합이다.

  0-비트 부호는 아무것도 없으니, 1-비트 부호는 곧 0과 1입니다. 앞에 0을 붙인 것과 1을 붙인 것의 집합이기 때문입니다. 이 재귀적 정의로부터, 우리는 n-비트 이진수들이 그레이 부호의 특성을 만족한다는 것을 입증할 수 있습니다. 

  첫째, 0을 붙이는 경우를 생각해봅시다. 0을 붙인 부분은 계속 0이므로 비트가 변하지 습니다. 또한 우리는 기존의 그레이 부호에 붙인 것이므로, 이들 역시 그레이 부호의 특성을 만족하여 단 하나의 비트만 계속 변하고 있을 것입니다. 나머지 반절 역시 같은 이유로 증명 가능합니다. 중요한 것은 가운데 접합부, 즉 앞쪽 절반의 마지막 부분과 뒷쪽 절반의 첫번째 부분입니다. 이 두 부호는 첫번째 비트만 달라지게 됨을 확인할 수 있습니다.

  이 재귀적 정의는 곧, 베케트의 스테이지 구성을 표현하는 <Beckett> 프로그램을 구현할 수 있게 만듭니다. <TowersOfHanoi>와 상당히 유사하죠. 재귀 호출의 두 번째 인자의 차이 빼고는 완전히 동일합니다.

프로그램 2.3.3: 그레이 부호

public class Beckett { public static void moves(int n, boolean enter) { if (n == 0) return; moves(n - 1, true); if (enter) StdOut.println("enter " + n); else StdOut.println("exit " + n); moves(n - 1, false); } }

% java Beckett 1
enter 1

% java Beckett 4
enter 1
enter 2
exit 1
enter 3
enter 1
exit 2
exit 1
enter 4
enter 1
enter 2
exit 1
enter 3
enter 1
exit 2
exit 1

  <TowersOfHanoi>는 방향이 필요했습니다. 원판의 개수가 홀수냐 짝수냐에 따라서 방향이 달라졌었죠. 하지만 입장과 퇴장에서 그런 것들은 고려하지 않아도 됩니다. 우리가 과거에 만들어보았던 <Ruler>를 기억하시나요? <TwoersOfHanoi>와 <Backett>는 <Ruler>를 재귀적으로 구현한 것과 상당히 유사합니다. 

  그레이 부호는 아날로그-디지털 변환부터 실험적 설계까지 다양한 분야에서 응용되고 있습니다. 펄스 부호 통신, 논리 회로의 최소화, 하이퍼큐브 아키텍처, 심지어 도서관 책을 정리하는 데에도 이용할 수 있습니다.

재귀적 그래픽

  간단한 재귀 그림은 굉장히 복잡한 그림을 꾸며낼 수 있습니다. 재귀 그림을 다루면서 다양한 응용프로그램과의 관계를 이해하고, 더 나아가 재귀 그림이 구체화되는 과정을 지켜보며 재귀적 프로그램의 특성을 쉽게 알아볼 수 있습니다. 

  첫번 째 간단한 예시는 <Htree>입니다. 명령행 인자로 n이 주어지면, n에 따른 H-tree를 그립니다. H-tree는 다음과 같습니다: n=0일 때에는 아무것도 그리지 않으며, 재귀적으로 그림을 그리기 시작합니다.

• 세 선분으로 H를 그립니다.
• n-1번째 시행에서 그려진 H의 각 끝부분 4곳에 H를 다시 그립니다.

  이런 그림은 실무에서의 수많은 응용프로그램과 깊은 관계를 맺고 있습니다. 예를 들어, 케이블 회사에서는 모든 집을 연결하기 위해 그 지역에서 적절한 분산을 통해 케이블을 배치해야 합니다. 이를 해결하는 합리적인 전략은 바로 H-tree입니다. 중심으로부터 적절히 분산되죠. 이와 비슷한 문제로, 컴퓨터 공학자들은 전력이나 신호를 적절히 전달하기 위해 집적회로 칩을 이와 같이 설계합니다.

  고정된 크기의 윈도우에서 그려지면서, H-tree는 완벽히 지수적으로 증가합니다. 4^n의 크기를 지니게 되며, n=10일 때 수백만, n=15일 때 수십억, n=30일 때는 프로그램이 도저히 끝나지 않는 상태까지 갈 것입니다.

  여러분이 <Htree>를 실행하고 그림이 완성되기까지, 여러분들은 어떤 식으로 그림이 그려지는지 관찰해볼 수 있을 것입니다. 이는 재귀 프로그램에 대한 통찰력을 제공하죠. 한 번 실행해보셔서 그림이 그려지는 순서에 대해 관찰해보세요. 

프로그램 2.3.4: Htree

public class Htree { public static void draw(int n, double sz, double x, double y) { // Draw an H-tree centered at x, y // of depth n and size sz. if (n == 0) return; double xO = x - sz / 2, xl = x + sz / 2; double yO = y - sz / 2, yl = y + sz / 2; StdDraw.line(xO, y, xl, y); StdDraw.line(xO, yO, xO, yl); StdDraw.line(xl, yO, xl, yl); draw(n - 1, sz / 2, xO, yO); draw(n - 1, sz / 2, xO, yl); draw(n - 1, sz / 2, xl, yO); draw(n - 1, sz / 2, xl, yl); } public static void main(String[] args) { int n = Integer.parseInt(args[0]); draw(n, .5, .5, .5); } }

  코드에서 각 StdDraw.line()과 draw()의 호출 순서에는 결과에 영향을 미치지 않음을 직접 수정해 확인해보세요. 어떤 StdDraw.line()과 어떤 draw()를 먼저 호출하느냐에 따라서 그림이 그려지는 순서는 달라질 수 있겠지만, 결과는 달라지지 않습니다.

브라운의 다리(Brownian bridge)

  H-tree는 프랙탈 모형의 간단한 예시였습니다. 프랙탈이란, 각 부분이 '크기가 작아진 원본'을 모방하며 반복되는 기하학적 모양을 의미합니다. 프랙탈은 재귀 프로그램을 통해 아주 쉽게 생성해낼 수 있습니다. 과학자, 수학자, 프로그래머들은 프랙탈을 각기 다른 시각에서 배우고 다룹니다. 우리는 <프로그램 2.2.3, IFS>를 통해서 이미 프랙탈을 몇 번 만나봤었죠.

  프랙탈에 대한 연구는 예술, 경제, 과학 등의 분야에서 중요한 역할을 지속적으로 해왔습니다. 예술가와 과학자들은 프랙탈을 이용하여 자연의 복잡한 모형들을 간단한 모델로 구성합니다. 구름, 식물, 산, 강줄기, 피부 등과 같은 것들을 기존의 기하학으로 묘사하는 것 대신에 프랙탈을 사용하죠. 경제학자들 역시 경제적 측정을 위해 프랙탈을 이용한 함수 그래프를 활용합니다.

  프랙탈 브라운 운동(Fractional Brownian motion)은 자연적으로 기복이 심한 모형에 대해 사실적인 프랙탈 모델을 만들기 위한 수학적 모델입니다. 신경막이나 파도와 같은 자연적 현상에 대해서 사용되기도 하고, 금융 전산에서 사용되기도 합니다. 주어진 현상에 대해 정확한 프랙탈을 계산하는 것은 어려운 도전이지만, 재귀 프로그램을 통해 비슷하게나마 만드는 것은 그다지 어렵지 않습니다. 

  <Brownian>은 브라운의 다리(Brownian bridge)로도 알려져 있는 간단한 프랙탈 브라운 운동의 근사 함수 그래프를 생성합니다. 여러분은 이 그래프를, (x0, y0)으로부터 (x1, y1)까지 무작위로 이동해서 도달하는 것이라고 생각해도 됩니다. 이는 중간점 이동 방법(midpoint displacement method)에 기반하여 구현되었습니다. 구간 [x0, x1]을 잇는 재귀적인 방법이죠.

• Base case: 두 점을 잇는 선분을 그립니다.
• Reduction case: 다음을 시행합니다.
• 주어진 구간의 중간점을 계산합니다. (x_m, y_m)이 될 것입니다.
• 0을 평균으로 하고, 인자로 주어진 분산을 따르는 무작위 정규 분포 값 delta를 y_m에 더합니다.
• 이를 하위 구간에 재귀적으로 적용하며, 이 때 분산은 인자로 주어진 스케일링 인수 s로 나누어 적용됩니다.

  쉽게 말하면, 하나의 선분을 계속 반절로 쪼개면서, 해당 중간점의 y좌표를 무작위로 변화시키는 것입니다. 이 모양은 두 매개변수에 의해 조절됩니다. 첫째는 변동성(volatility, 분산의 초기값)으로, 중간점이 이탈하는 정도를 제어합니다. 둘째는 허스트 지수(Hurst exponent)로, 곡선의 부드러움을 제어합니다.

프로그램 2.3.5: Brownian Bridge

public class Brownian { public static void curve(double x0, double y0, double x1, double y1, double var, double s) { if (x1 - x0 < .01) { StdDraw.line(x0, y0, x1, y1); return; } double xm = (x0 + x1) / 2; double ym = (y0 + y1) / 2; double delta = StdRandom.gaussian(0, Math.sqrt(var)); curve(x0, y0, xm, ym + delta, var / s, s); curve(xm, ym + delta, x1, y1, var / s, s); } public static void main(String[] args) { double H = Double.parseDouble(args[0]); double s = Math.pow(2, 2 * H); curve(0, .5, 1.0, .5, .01, s); } }

  우리는 허스트 지수를 H로 표시하며, 각 재귀 레벨에서 분산을 2^2H로 나누게 됩니다. H가 0.5일 때의 곡선을 브라운의 다리라고 합니다. 도박꾼의 파산 문제(프로그램 1.3.8)의 연장 버전이라고 생각하시면 될 것 같네요. H가 0.5보다 작은 경우, 이동이 점점 격해지며 고르지 않은 분포가 나타납니다. H가 0.5보다 큰 경우, 부드러운 곡선이 나타납니다. H가 2의 값을 가질 때, 이는 곡선의 프랙탈 차원(fractal dimension)을 나타내는 것으로 알려져 있습니다.

  이러한 중간점 이동 방법을 2차원으로 확장하면, 플라즈마 구름을 생성해낼 수 있습니다. 직사각형의 플라즈마 구름을 그리고, 재귀적인 방법을 통해 사각형을 사등분 하여 그 색을 각기 변화시키는 것입니다. 이러한 방법으로 꽤 사실적인 구름을 생성해낼 수 있습니다. 이런 방식의 변형들을 이용하여 영화, 컴퓨터 게임 등의 배경을 생성하는데 활용하기도 합니다.

플라즈마 구름

재귀의 주의사항(Pitfalls of recursion)

  이쯤 되면, 여러분들은 재귀 프로그램들이 얼마나 간단하고 우아한 프로그램들을 만들어낼 수 있는지 느꼈을 것입니다. 여러분들이 자신만의 재귀 프로그램을 작성하기 전에, 반드시 짚고 넘어가야할 사항들이 있습니다. 

Base case의 부재

  다음 재귀 함수를 생각해보세요. 조화수를 계산하는 함수이지만, base case가 존재하지 않습니다.

public static double H(int N) { return H(N - 1) + 1.0 / N; }

  이 함수를 여러분이 클라이언트로서 실행하게 된다면, 이것은 영원히 자기 자신을 호출하죠. 여러분들은 이미 이전에 무한 반복문을 만나본 적이 있을 것입니다. 무한 재귀는 무한 반복과 살짝 다릅니다. 함수의 특성 상, 함수 종료 시 반환해야 하는 위치를 기억해야 합니다. 따라서 시스템이 각 재귀 호출에 대해 일일이 추적해야 하고, 이는 메모리를 소모하는 일입니다. 결국 자바는 주어진 모든 메모리를 소모하고 StackOverflowError를 일으키게 됩니다. 

수렴의 부재

  또 다른 흔한 문제는 재귀의 호출이 기존 문제보다 작은 특정한 점에 수렴하지 않는 것입니다. 예를 들어, 다음 메소드는 인자가 1일 때를 제외하곤, 무한한 재귀 반복에 빠지게 됩니다. 

public static double H(int N) { if (N == 1) return 1.0; return H(N) + 1.0/N; }

지나친 메모리 사용

  재귀적으로 함수를 호출할 때, 시스템은 각 재귀 호출을 추적하기 위해 메모리를 소모합니다. 여러분은 재귀 함수가 너무 많이 자신을 재귀적으로 호출하게 되어, 주어진 모든 메모리를 소모하는 일이 없도록 해야 합니다.

불필요한 계산의 반복

  재귀 프로그램은 이해하기 쉽고, 작성하기 간단합니다. 그렇다고 해서 어떤 문제를 해결하든 간에 재귀적으로 접근하는 것은, 불필요한 계산을 반복하는 것일지도 모릅니다. 여러분은 재귀 프로그램을 작성할 때 언제나 심사숙고해야 하며, 재귀적인 방법보다 더 효율적인 방법이 있음을 명심해야 합니다. 예를 들어, 피보나치 수열을 봅시다.

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377...

  이는 n>1인 정수에 대해 F_n = F_n-1 + F_n-2 이며, F₀ = 0, F₁ = 1입니다. 피보나치 수열은 자연에서 많이 찾아볼 수 있는 흥미로운 수열입니다. 초보 프로그래머가 피보나치 수열을 계산하기 위해 다음과 같은 프로그램을 작성했다고 해보죠.

public static long F(int n) { if (n == 0) return 0; if (n == 1) return 1; return F(n - 1) + F(n - 2); }

  하지만, 이 프로그램은 굉장히 비효율적입니다. 초보 프로그래머는 이 사실을 인정하지 못하고, 컴퓨터가 답을 찾을 수 있을 정도로 충분히 빠르다는 전제 하에 이런 코드를 작성합니다. 그러지 마세요. 

  F(8)은 21입니다. 이를 계산하기 위해서 F(7)과 F(6)을 계산해야 하죠. F(7)은 어떻게 계산할 수 있을까요? F(6)과 F(5)를 계산하는 일입니다. 또 F(6)은 F(5)와 F(4)를 계산해야 하는데, F(5)는 이전에 F(7)을 계산할 때 계산되었음에도 불구하고 또 다시 계산을 해야하죠. F(1)에 도달하기까지, 이런 불필요한 계산의 반복이 수도 없이 이루어질 것입니다.

잘못된 피보나치 수 계산법

  F(200)을 계산하기 위해서 F(1)은 얼마나 계산되어야 할까요? 10^43번 이상입니다. 이렇게 많은 계산을 할 수 있는 컴퓨터는 상상조차 할 수 없네요. 재귀적 프로그램은 지수적 시간을 소모한다는 사실을 잊지 마세요. 재귀의 함정에 빠져 프로그램을 비효율적으로 작성하지 않길 바랍니다.

  메모이제이션(memorization)이라는 체계적인 기법을 통해, 이런 문제들을 해결할 수 있습니다. 간단한 재귀 프로그램들은 이 기법으로 대체 가능하죠. 이미 계산된 값들은 배열에 저장해 재사용하고, 새롭게 계산할 값들만 직접 계산하는 것입니다. 이미 해결한 문제는 다시 해결하지 않는다, 이 기법은 동적 프로그래밍(dynamic programming)의 철학입니다. 이를 기억하세요.

재귀를 바라보는 관점

  재귀를 절대 사용하지 않는 프로그래머들은 두 기회를 놓치는 것입니다. 첫째, 재귀는 복잡한 문제의 간단한 해결책을 제시합니다. 둘째, 재귀적 해결책은 프로그램이 정상적으로 작동한다는 근거를 포함합니다. 컴퓨터의 초창기에는, 재귀 프로그램으로 발생하는 오버헤드(overhead, 함수 호출로 인한 비용) 때문에 많은 사람들이 재귀를 피했습니다. 하지만 현대 시스템에서, 재귀는 꽤 괜찮은 방법이 되었습니다.

  생각해보세요. 여러분들은 간단한 재귀 함수만으로, 챕터 1에서 배웠던 반복문, 조건문, 배열들을 활용하는 프로그래밍 모델을 손쉽게 구현할 수 있었습니다. 또한 재귀는 우리의 프로그램이 의도한 대로 작동한다는 믿음을 줍니다. 수학적 귀납법으로 완벽히 증명한 후 사용할 수 있기 때문이죠. 현대의 응용프로그램들은, 그 규모가 굉장히 거대해지면서 해당 프로그램이 정확히 작동한다는 것을 보증하기 힘들 때가 있습니다. 재귀는 이러한 부분에서 엄청난 효과를 자랑합니다.

  재귀는 우리가 이제껏 배워왔던 프로그래밍 모델의 마지막 항목이었습니다. 여지껏 배웠던 것들은, 20세기 컴퓨팅 인프라를 구축하기 위해 사용되었던 것들이죠. 프로그램은: 각 기본 자료형, 조건문, 반복문, 함수 호출에서 작동하는 구문(statements)을 지닌 함수의 라이브러리들로 구성됩니다. 다음 챕터에서는, 이 부분을 더욱 더 강조하고 거대한 응용프로그램의 측면에서 이를 재조명해볼 것입니다. 챕터 3과 챕터 4는 현대 프로그래밍을 지배하고 있는 객체지향이라는 관점으로 우리의 생각을 확장해볼 것입니다.

끝.