과학

자바로 프로그래밍에 입문할래요: 2.3. 재귀 (2)

 이로서 2장은 끝. 3장부터는 객체지향 개념을 본격적으로 배우기 시작할 거야.

재귀를 흔히 '비효율적인 방법'으로 생각하는 경우도 많은 것 같아.

하지만 재귀는 때때로 아주 강력하고,  현대에 와서는 재귀의 최적화 방법도 다양하게 등장하고 있어.

 

재귀를 활용하는 것은 프로그래머의 역량이 드러나는 부분이기도 해.

가령 마지막에 비효율적인 재귀의 예시로 나타나는 피보나치 수열의 경우도,

알고리즘을 잘 구성해 선형(linear)적으로 재귀를 활용하거나

메모이제이션 기법 등을 활용하면 자바에서도 꽤나 괜찮은 성능을 낼 수 있어.

 

2.3. 재귀 (1)

2.2. 라이브러리와 클라이언트 (3)

2.2. 라이브러리와 클라이언트 (2)

2.2. 라이브러리와 클라이언트 (1)

2.1. 정적 메소드 (2)

2.1. 정적 메소드 (1)

1.5. 입출력 (2)

1.5. 입출력 (1)

1.4. 배열 (3)

1.4. 배열 (2)

1.4 배열 (1)

1.3. 조건문과 반복문 (2)

1.3. 조건문과 반복문 (1)

1.2. 내장 자료형 (2)

1.2. 내장 자료형 (1)

0.0. 여는 글, 1.1. 첫 프로그램 만들기

 

================================

 

그레이 부호(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: 다음을 시행합니다.
    • 주어진 구간의 중간점을 계산합니다. (xm, ym)이 될 것입니다.
    • 0을 평균으로 하고, 인자로 주어진 분산을 따르는 무작위 정규 분포 값 delta를 ym에 더합니다.
    • 이를 하위 구간에 재귀적으로 적용하며, 이 때 분산은 인자로 주어진 스케일링 인수 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인 정수에 대해 Fn = Fn-1 + Fn-2 이며, F0 = 0, F1 = 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는 현대 프로그래밍을 지배하고 있는 객체지향이라는 관점으로 우리의 생각을 확장해볼 것입니다.

 

끝.

24개의 댓글

2021.07.14

피보나치는 지역변수 2개로 해결하라구

0
2021.07.14

재귀 할꺼면 꼬리재귀도 같이 설명하자

0
2021.07.15
@치킨맨9

꼬리 재귀의 경우 자바와는 관계가 적은 내용인지라..ㅎㅎ

0
2021.07.15
@스비니

jvm단에서는 지원하는데 jdk단에서 지원하지 않는다 정도

0
2021.07.14

완벽히 이해 하지 못한다면 안쓰는게 나은 함수..

1
2021.07.14

근데 이런거는 어따쓰냐 개발할떄

0
2021.07.14
@코등이

나는 트리구조 데이터 찾을때 쓴거 같은데

최상위 노드에서 특정노드 찾을때 재귀함수씀

0
2021.07.14
@코등이

제시해주는 예시들은 전부 특정 분야에서 실제로 사용되는 예시들이야.

보통 Composite 구조를 가진 클래스들이라면 재귀를 통해 손쉽게 여러가지 일들을 해결할 수 있어.

(가령, 특정 폴더 안의 모든 폴더와 파일을 순회하는 경우)

혹은 스택을 이용해서 무언가를 할 때 손쉽게 적용할 수 있지.

0
2021.07.16
@코등이

어떤 문제를 작은 부분 문제들로 분리했을 때

 

작은 문제를 푸는 방식이 큰 문제를 푸는 방식과 동일한 상황에 쓰는 경우가 많아

 

근데 이런 상황이 비일비재한건 아니라서 자주 쓰진 않음

0
2021.07.15

한남 재귀해라 이기

 

3
2021.07.15
@파드

어이 없네 진짜 ㅋㅋㅋㅋㅋㅋㅋㄱㅋ

0
@파드

아 피식했다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

0
2021.07.15

재귀는 가급적이면 안쓰는게 좋다

조금만 실수해도 메모리 펑 터짐

그리고 버그 터졌을 때 디버깅 난이도가 굉장히 높음

0
2021.07.15
@1일4식

내 짧은 지식으로는, 디버깅 난이도가 높다는 건 동의할 수가 없네. 디버거로 일일히 콜스택을 따라가는 건 물론 어렵겠지만..

 

재귀의 기막힌 장점 중 하나는 가독성과 검증용이성임. 일반적인 반복문 로직보다 훨씬 그 코드가 적고, 점화식을 잘 다루는 프로그래머라면 수학적인 검증 역시 훨씬 더 쉽게 해낼 수 있어. 이런 검증을 거치지 않은 재귀는 버그의 가능성이 높겠다만, 검증이 잘 이루어진 재귀는 ‘로직’으로 인한 버그를 원천 차단할 수 있다고 생각해.

0
2021.07.15
@스비니

로컬에서 한줄씩 디버깅하면야 할수야 있지

대부분의 자바 어플리케이션은 웹 백엔드로 쓰이기 때문에 서버 상에서 로그를 보고 추적하는 수밖에 없음

트래픽이 어마어마해지면 어떤 데이터가 언제 들어갈지 예측하는게 굉장히 어려운 일이야

 

만약 프로덕션으로 사용되는 코드에서 재귀를 사용하고 있고, "아주 특별한 케이스" 에서 무한루프가 발생한다고 해보자.

재귀 무한루프는 콜스택을 무한으로 파고들어가면서 메모리를 터트려버리는데 그럼 바로 장애터지고 난리가 남

그럼 바로 긴급 수정 들어가야 하는데 디버깅이 어려우면 어떻게 될까?

특별한 케이스인 경우 재연 자체가 어려운 경우도 있어서 위험성을 안고 가야할 가능성도 있지

 

그런 상황에서 디버깅이 잘 될거라고 장담할 수 있어?

 

게다가 재귀 코드는 한 눈에 보고 파악하기 어려워

코드 양이 적은건 분명 장점이지만 프로덕션 레벨로 가면 큰 장점은 아님

코드의 양보다는 이해하기 쉬워야 해

가독성이 좋아야 이해가 쉽고 생산성이 좋아진다

이해하기 어려운 코드는 미래의 자신이나 다른 누군가가 수정할 때 잘못 수정할 가능성이 커진다

 

또 프로덕션 코드를 유지보수하다보면 성능이나 가독성 개선을 위해 예전에 짠 코드를 재구성하는 일이 꽤 많음

근데 이거 자체가 굉장히 시간 비용이 많이 들어가는 일이야

내가 바꾼 로직이 전 로직하고 동일함이 보장되어야 하기 때문이지

웹 서비스업에서 프로덕션 코드 분량 이상의 테스트 코드를 작성하는덴 다 이유가 있는거야

테스트 코드 유지보수를 위한 비용이 꽤 큰데도 말이야

 

그런걸 생각해보면 최초 코드 작성 단계부터 이해하기 어려운 코드는 사용을 안하는게 더 낫다

 

재귀가 절대악이란게 아니야

장점도 있지만 단점이 그보다 더 크기 때문에 아주 간단한 재귀가 아닌 한 지양하자는 말임

0
2021.07.15
@1일4식

“아주 특별한 케이스”에서 무한루프가 발생한다는 것 자체가, 수학적 귀납법을 제대로 적용하지 못했다는 의미임. 제대로 검증을 거치지 않고 사용할 재귀라면, 말마따나 사용하지 않는 게 낫다는 건 동의함. 재귀는 위험하니깐 철저한 검증 없이 사용하면 안 됨. 역량의 차이가 철저히 드러나는 부분 중 하나가 바로 재귀라고 생각해. 세상엔 워낙 요상한 경우들이 많으니깐 말하기 조심스럽지만, Base Case와 Induction Step이 명확하게 있는 재귀에서 무한 호출이 발생한다면, 그건 재귀 활용을 제대로 하지 못했다 말할 수 밖에..

 

가독성이 좋고 나쁘고의 이야기는 별로 할 말은 없네. 어느 누구는 재귀가 가독성이 좋다고 말하고, 그렇지 않다고 느끼는 사람들도 많은 것 같아. 난 재귀를 사용하는 것이 훨씬 가독성을 높여준다고 생각해. 이건 재귀가 얼마나 익숙한지나 코드를 머릿속에서 어떻게 읽는지에 따라 다를 수 있으니 더 이상 이야기는 안 할게.

 

리팩토링에 대한 이야기도 결국 가독성 이야기의 연장이니 생략. 테스팅이나 커버리지에 대한 이야기는, 지금 이야기하는 재귀의 효용과는 관계가 적은 이야기인 것 같네..

 

모든 코드에서 실제 재귀가 사용되는 부분의 비율은 아마 상당히 적을 거야. 그만큼, 재귀는 적절한 때에 써야해. 아무렇게나 검증 없이, 무분별하게 사용한다면 너가 말한 부작용이 필연적으로 생기겠지. 장점을 하나도 활용하지 못하고 단점만이 남는 코드가 될 거야. 의견 고마워.

0
2021.07.15
@1일4식

선생님 어떤 알고리즘을 채택해서 해결 해야 하느냐에 따라 다른 거지

재귀를 가급적 안 쓰는게 좋은 것이 아닙니다요..

 

특히 대다수의 NP 문제들은 대부분 최적 알고리즘을 도출할 수 없는 것으로 이미 수학적 증명이 되었기 때문에

백트래킹이나 그리디 알고리즘 등으로 설계해서

재귀를 많이 사용할 수 밖에 없습니다요

0
2021.07.15

좋은 글 감사합니다.

0

재귀해!

0
2021.07.15

이귀이귀 공머충 재귀하라 이기야

0
2021.07.16

재커 너무 어려워요. 개념보다 문제가 더 어려워

0
2021.07.16

정렬알고리즘은 안나오네 ㅋㅋ 퀵소트라도 나올줄 알았는데

0

우앙

0
@세균없는세균맨

나중에 파서에 대해서도 써줘!!!

0
무분별한 사용은 차단될 수 있습니다.
번호 제목 글쓴이 추천 수 날짜
522 [과학] 한반도 형성 모델 8 白猫 4 22 일 전
521 [과학] 인류 발전은 정체되었는가? 119 월급받으며개드립하기 22 27 일 전
520 [과학] 자바로 프로그래밍에 입문할래요: 3.3. 자료형 설계하기 (4) 스비니 5 2021.08.21
519 [과학] 자바로 프로그래밍에 입문할래요: 3.3. 자료형 설계하기 (3) 3 스비니 3 2021.08.17
518 [과학] 자바로 프로그래밍에 입문할래요: 3.3. 자료형 설계하기 (2) 2 스비니 0 2021.08.15
517 [과학] 자바로 프로그래밍에 입문할래요: 3.3. 자료형 설계하기 (1) 9 스비니 1 2021.08.12
516 [과학] 자바로 프로그래밍에 입문할래요: 3.2. 자료형 생성하기 (3) 스비니 0 2021.08.11
515 [과학] 모든 멸종의 어머니 - 페름기 대량절멸 (1) 9 PorcupineTree 10 2021.08.11
514 [과학] 희귀 혈전등에 대한 아스트라제네카 코로나 19 백신 접종의 ... 18 매콤챱스 5 2021.08.10
513 [과학] 자바로 프로그래밍에 입문할래요: 3.2. 자료형 생성하기 (2) 2 스비니 2 2021.08.09
512 [과학] 엔트로피는 감소할 수 있는가? 43 Kuqi 21 2021.08.08
511 [과학] 자바로 프로그래밍에 입문할래요: 3.2. 자료형 생성하기 (1) 3 스비니 2 2021.08.05
510 [과학] 자바로 프로그래밍에 입문할래요: 3.1. 자료형 (4) 11 스비니 3 2021.08.04
509 [과학] 자바로 프로그래밍에 입문할래요: 3.1. 자료형 (3) 2 스비니 3 2021.08.02
508 [과학] SF스압) 최후의질문 / 원래는..(How It Happened) 16 기타치는고라니 16 2021.07.31
507 [과학] [양자역학 3부] 슈뢰딩거의 고양이에 대해서. 28 기타치는고라니 3 2021.07.30
506 [과학] 자바로 프로그래밍에 입문할래요: 3.1. 자료형 (2) 2 스비니 3 2021.07.29
505 [과학] (기상)우리나라 더위의 발생 형태 4가지. 51 마리괭이 20 2021.07.25
504 [과학] 자바로 프로그래밍에 입문할래요: 3.1. 자료형 (1) 4 스비니 1 2021.07.22
503 [과학] 자바로 프로그래밍에 입문할래요: 2.3. 재귀 (2) 24 스비니 5 2021.07.14