재귀 알고리즘 기본
지난 글 : [알고리즘/Do it 알고리즘] - 큐
재귀란?
어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용해 정의하고 있을 때 이를 재귀적(recursive)이라 한다. 이런 재귀의 개념을 사용하면 1부터 시작해 2, 3, ... 처럼 무한히 계속되 자연수를 아래와 같이 정의할 수 있다.
- 1은 자연수다.
- 자연수 n의 바로 다음 정수도 자연수다.재귀적 정의(recursive defintion)를 사용해 무한으로 존재하는 자연수를 위의 두 문장으로 정의했다. 재귀를 효과적으로 사용하면 이런 정의뿐 아니라 프로그램도 간결하게 작성할 수 있다.
팩토리얼 구하기
재귀를 사용한 예로 음이 아닌 정수의 팩토리얼(fantorial)값을 구하는 프로그램을 만들어보자. 음이 아닌 정수 n의 팩토리얼(n!)은 아래와 같이 재귀적으로 정의할 수 있다.
- 0! = 1
- n > 0이면 n! = n x (n - 1)!10의 팩토리얼인 10!은 10 x 9!로 구할 수 있고, 그 우변에서 사용한 식 9!은 9 x 8!로 구할 수 있다.
factorial 메서드가 반환하는 값을 아래와 같다.
- 매개변수 n에 전달받은 값이 0 보다 클 때: n * factorial(n - 1)
- 매개변수 n에 전달받은 값이 0 보다 크지 않을 때: 1이 메서드의 본문은 조건 연산자를 사용해 아래처럼 한 줄로 구현할 수 있다.
재귀 호출
factorial 메서드를 실행해 4의 팩토리얼값을 구하는 과정이다.
1. 메서드 호출식 factorial(4)를 실행해 factorial 메서드가 시작된다. 이 메서드는 매개변수 n에 3을 전달받아
4 * factorial(3)을 반환한다. 이 곱을 수행하기 위해 3을 매개변수로 factorial 메서드를 호출한다.
2. 호출된 factorial은 매개변수 n에 3을 전달받는다. 다시 3 * factorial(2)를 수행하기 위해 factorial
메서드를 호출한다.
3. 다시 호출된 factorial은 매개변수 n에 2를 전달받는다. 다시 2 * factorial(1)을 수행하기 위해
factorial 메서드를 호출한다.
4. 다시 호출된 factorial은 매개변수 n에 1을 전달받는다. 다시 1 * factorial(0)을 수행하기 위해
factorial 메서드를 호출한다.
5. 호출된 factorial은 매개변수에 전달받은 값이 0이므로 1을 반환한다. 이때 return문이 처음 실행된다.
6. 반환된 값 1을 전달받은 factorial 메서드는 1 * factorial(0), 즉 1 * 1을 반환한다.
7. 위 과정을 4 * factorial(3)까지 반복한다. 4 * factorial(3)에서 4 * 6이 수행된다.
8. 이제 팩토리얼값 24를 얻는다.
직접 재귀와 간접 재귀
factorial 메서드는 그 내부에서 factorial 메서드를 호출한다. 이처럼 자신과 동일한 메서드를 호출하는 것을 직접(direct)재귀라 한다. 이와 달리 간접(indirect) 재귀는 메서드 a가 b를 호출하고, 다시 메서드 b가 a를 호출하는 구조다.
재귀 알고리즘에 알맞은 경우는 '풀어야 할 문제', '계산할 메서드', '처리할 자료구조'가 재귀로 정의되는 경우다.
유클리드 호제법
두 정수의 최대공약수(greatest common divisor)를 재귀적으로 구하는 방법을 알아보자. 두 정수를 직사각형 두 변의 길이라 생각하면 두 정수의 최대공약수를 구하는 문제는 아래처럼 바꿀 수 있다.
직사각형을 정사각형으로 빈틈 없이 채운다. 이렇게 만들어지는 정사각형 가운데 가장 긴 변의 길이를 구하라.22 X 8 크기의 직사각형을 직사각형 A로 하는 문제를 풀어보자.
1. 22 X 8 크기의 직사각형에서 짧은 변(8)을 한 변으로 하는 정사각형으로 직사각형을 분할한다.
이를 수행하면 8 X 8 크기의 정사각형이 2개 생긴다. 8 X 6 크기의직사각형이 1개 남는다.
2. 남은 8 X 6 크기의 직사각형을 다시 같은 과정으로 분할한다.
6 X 6 크기의 정사각형이 1개 생긴다. 6 X 2의 직사각형이 1개 남는다.
3. 다시 남은 6 X 2 크기의 직사각형을 같은 과정으로 분할한다. 2 X 2 크기의 정사각형 3개로 나누어진다.
여기서 얻은 2가 최대공약수다. (정사각형만으로 구성했을 때 변의 길이가 최대공약수)이렇게 두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 때 나누어떨어지면 그중 작은 값이 최대공약수다. 나누어떨어지지 않으면 작은 값과 나머지로 나누어떨어질 때까지 같은 과정을 재귀적으로 반복한다.
이 과정을 수학적으로 표현하기 위해 두 정수 x, y의 최대공약수를 gcd(x, y)로 표기한다. x = az와 y = bz를 만족하는 정수 a, b와 정수 z가 존재할 때 z를 gcd(x, y)라 할 수 있다. 이를 정리하면 최대공약수는 아래와 같이 구할 수 있다.
- y = 0일 때 최대 공약수: x
- y != 0일 때 최대공약수: gcd(y, x % y)이 알고리즘을 유클리드 호제법(euclidean method of menual division)이라 한다. 아래는 유클리드 호제법으로 두 정수의 최대공약수를 구하는 프로그램이다.
위 메서드 gcd(22, 8)을 해석해보자.
1. gcd(22, 8)에서 매개변수 y에 전달받은 값이 0이 아니므로 gcd(8, 22 % 8(6))을 호출한다.
2. 위에서 호출된 gcd(8, 6)은 다시 gcd(6, 8 % 6(2))가 호출한다.
3. 다시 위에서 호출된 gcd(6, 2)은 다시 gcd(2, 6 % 3(0))을 호출한다.
4. 위에서 호출된 gcd(2, 0)은 매개변수 y에 전달받은 값이 0이므로 매개변수 x(2)를 반환한다.
5. 22와 8의 최대공약수를(2) 얻었다.
참고 서적 :
