알고리즘 - 재귀 :: 유클리드 호제법(최대공약수), 피보나치, 팩토리얼

강의 소개

현재 수강하고 있는 멀티캠퍼스 k-digital 지능형 웹서비스 풀 스택 과정을 수강하며 적은 내용입니다.

교재로는 자료구조와 함께 배우는 알고리즘 입문 자바 편을 사용하고 있습니다.

---

재귀(recursive)

재귀 함수

어떤 함수 내부에 자기 자신 함수를 포함하고 있는 함수이다.

재귀 함수를 사용할 때, 조건문으로 종료 조건을 주거나(재귀 함수를 호출하지 않는 조건), 아니면 자기 자신을 계속 호출해야 한다.

 

 

재귀를 사용한 예제 코드

1. 팩토리얼

[재귀 함수 코드 구현]

static int factorial(int num) {
	// num 변경하여 같은 메서드 계속 호출 
	System.out.println("===" + num + "일 때 factorial 시작===");
	// 종료조건
	if (num == 0 || num == 1) return 1;
	System.out.println("===" + num + "일 때 factorial종료===");
	return num * factorial(num-1); // 재귀 호출
}

팩토리얼은 누적곱이다. 만약 5! 을 구한다고 하면

1 * 2 * 3 * 4 * 5가 된다. 따라서 5! 은 4! * 5와 같다. 따라서 코드에서 리턴 값을 아래와 같이 주었다.

return num * factorial(num-1);

 

다만, num이 계속 -1 되어 1이 되는 순간은 곱셈을 멈춰야 한다. 1을 계속 곱해도 의미가 없기 때문이다.

따라서 아래와 같이 num일 때는 재귀 함수 호출을 하지 않고, 1을 리턴한다.

 

또한, 이 코드가 중요한 점은 재귀 함수가 조건 없이 자기 자신을 계속 호출한다면, 무한루프에 빠지게 된다.

그래서 반드시 if조건문으로 재귀 함수의 종료지점을 명시해야 한다. 

if (num == 0 || num == 1) return 1;

 

 

2. 유클리드 호제법

이는 두 수 a, b 간의 최대 공약수를 구하는 공식이다.

출처: 위키백과

 

다시 정리하면 아래와 같다. 

 

 

[반복문 코드 구현]

a = 18;
b = 12;
while(true) {
	int remain = a % b;
	if(remain == 0) break;
	a = b;
	b = remain;
	}

반복문으로 코드를 구현하면 위와 같다.

무한 루프를 돌려 계속 두 수 a, b를 나누고 (단, a > b) 그 나머지가 0이 될 때까지 반복한다.

이 코드를 재귀 함수로 바꾸면 아래 코드가 된다.

 

[재귀 함수 코드 구현]

static int gcd(int a, int b) {
	System.out.println(a + ":" + b);
	int remian = a % b;  // a와 b를 나눈 나머지 r
	if(remain == 0) return b;
	// a와 b을 나눈 나머지를 구하는 반복. 그 나머지가 0이 될 떄까지.
	return gcd(b, remain); 
}

앞서 보았듯 유클리드 호제법은 a와 b 즉, 두 수를 나눈 뒤, 나머지를 계속 나누는 작업이었다.

그래서 a자리에는 b를 넣고, b자리에는 remain을 계속 넣어주는 과정의 반복이다. 따라서 아래와 같은 코드로 재귀 함수를 호출한다.

return gcd(b, remain);

이 과정은 remain이 최종적으로 0이 될 때까지 이뤄진다.

그리고, remain이 되기 직전의 b가 우리가 구하는 최대 공약수가 된다. 

if(remain == 0) return b;

이때, 주의해야 할 점은 무한 루프이다.

만약 if조건으로 더 이상 재귀 함수를 호출하지 않는 문장이 없다면, 재귀 함수는 무한 루프에 빠지게 되어 유의해야 한다.

 

 

3. 피보나치수열

출처: 나무위키

피보나치의 경우 아래 사진과 같이, 앞선 두 수를 계속 더하는 과정의 반복이다.

출저: 나무위키

 

[반복문 코드 구현]

피보나치는 0을 생략하고 1부터 시작하기도 한다.

그 코드를 반복문으로 10항까지 구현하면 아래와 같다.

int i1 = 1;
int i2 = 1;
System.out.println("1항의 수열 값은 = " + i1);
System.out.println("2항의 수열 값은 = " + i2);
		
for (int i = 3; i <= 10; i++) {
	int result = i1 + i2;
	System.out.println(i + "항의 수열 값은 = " + result);
	i2 = i1; 
	i1 = result;
	}

 

 

[재귀 함수 코드 구현]

static int fibo(int n) {
	if (n == 1 || n == 2) return 1;
	//리턴 1이 나올 때까지, 앞의 두 항을 더한다.
	return fibo(n - 2) + fibo(n - 1);  
}

재귀 함수로 피보나치를 구현한 코드이다. 훨씬 간결해지며, 동일한 결과를 보여준다.

n에는 몇 항까지 구현할 것인지 넣어주고, 만약 1 또는 2가 입력되면 1, 2번째 항(=값)은 1이므로 재귀 호출 없이, 1을 리턴한다.

 

특이한 점은, 이 fibo메서드는 자기 자신을 2번씩 호출한다.

만약 메인 메서드에서 fibo(4)를 하는 경우를 생각하면 아래와 같다.

fibo(4)	fibo(2) == 1
	fibo(3)	fibo(1) == 1
		fibo(2) == 1

만약 fibo(4)를 호출하면 내부에서 동일한 fibo(2)를 두 번 호출하게 된다.

따라서 같은 것이라도 여러 번 계산해야 하므로 메모리를 많이 낭비한다. 따라서 피보나치는 재귀보다 반복문이 더 효율적이다.

 

 

재귀와 top-down, bottom-up

 

top-down 방식

꼭대기부터 분석해서 아래로 내려가는 방식이다.

ex. 팩토리얼

재귀호출로 구현하는 것이 좋다.

 

bottom-up 방식

같은 항을 계산하는 메서드를 여러 번 호출한다.

이런 경우 반복문 사용이 더 적합하다. 계산을 저장해서 재사용할 수 있기 때문이다.

ex. 피보나치