순환(Recursion)
순환이란 무엇일까? 순환은 간단하다. 자기 자신을 호출하는 루틴을 모두 순환, 즉 재귀 호출이라고 한다. 순환의 대표적인 예로는 팩토리얼 값 구하기, 피보나치 수열, 이항계수, 하노이의 탑, 이진탐색 등이 있다. 오늘은 순환, 순환과 비슷한 반복을 이용하여 팩토리얼, 거듭제곱, 피보나치 수열을 구현해보고자 한다.
순환식은 다음과 같이 정의할 수 있다.
- 순환식의 정의
- 순환부 : 문제의 크기가 점차 작아짐
- 종료부 : 순환호출 정지,
종료 조건(true : 순환호출 정지, 계산된 값 반환 / false : 순환 호출)
이러한 순환식의 정의를 이용하여 팩토리얼 값을 구하는 프로그래밍을 구현해보자.
팩토리얼 프로그래밍
- 팩토리얼의 정의
팩토리얼은 종료 n이 1보다 작거나 같은 경우와 n이 1보다 큰 경우로 나누어 생각할 수 있다. 사실 순환이 아니더라도 for문을 이용하면 쉽게 구현할 수 있다. 우선 for문으로 구현하는 방법에 대해 알아보자.
for문으로 구현하기
for문을 이용해서 1~n까지의 곱을 구하는 방법으로 프로그래밍을 해보자.
public static int for_factorial(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
System.out.println(result +" x "+ i +" = " + result*i);
result = result * i;
}
return result;
}순환(재귀)로 구현하기
아래의 코드는 순환을 이용해서 n!의 (n-1)!을 현재 작성중인 함수 내에서 다시 호출하여 계산하는 방법을 활용한 것이다.
public static int re_factorial(int n) {
if (n <= 1) {
return 1;
} else {
System.out.println("factorial("+n+")");
return n*re_factorial(n-1);
}
}위의 두 함수를 main()에서 함께 실행해보면 같은 결과가 출력되는 것을 확인할 수 있다.
public static void main(String[] args) {
int n=5;
System.out.println(n+"! = " + for_factorial(n) + "\n");
System.out.println(n+"! = " + re_factorial(n));
}
순환 vs 반복
컴퓨터에서의 되풀이 방법에는 2가지가 있다.
- 순환(recursion) : 순환 호출 이용하기
- 반복(iteration) : for문이나, while문을 이용하기
대부분의 순환은 반복으로 바꾸어 작성할 수 있다. 순환이 적합할 때도 있는 반면 오히려 순환을 이용하면 반복을 사용했을 때에 비해 속도도 떨어지고 메모리 낭비가 심해질 수도 있다. 그렇다면 반복이 아닌 굳이 재귀함수를 사용하는 이유는 무엇일까?
재귀함수를 사용하는 이유?
사실 필자도 아직까지는 재귀함수를 이용하면 좋은 점에 대해 확실히 이해하지 못했다. 언제나 반복을 사용하는 것이 옳은 경우는 아니며, 때때로 순환을 이용하는 것이 오히려 좋은 방법일 수 있기 때문이다.
재귀함수를 이용하면 보다 간결한 코드를 작성할 수 있어 코드의 가독성을 높일 수 있고, 동적 프로그램이나 그래프 탐색 알고리즘 등의 특정 개발에 있어서는 훨씬 유리할 수 있다고 한다. 재귀함수의 사용 이유에 대한 사람들의 논의 내용을 해당 사이트에서 한번 읽어보자. 아래의 사진은 익명의 사용자가 남긴 글이 인상적이어서 첨부했다.
거듭제곱 프로그래밍
순환이 반복보다 효율적임을 보여주는 예시가 바로 '거듭제곱 프로그래밍'이다. 숫자 x의 n제곱값(x^n)을 구하는 문제를 생각해보자.
반복으로 구현하기
반복적인 방법이라면 다음과 같이 함수를 작성할 수 있다.
public static double for_power(double x, int n) {
int i;
double r = 1.0;
for(i=0; i<n; i++) {
r = r*x;
}
return(r);
}순환으로 구현하기
순환으로 구현 할 때에는 n이 0인 경우, 짝수인 경우, 홀수인 경우로 나누어 생각할 수 있다. 
- n이 짝수일 때의 계산법
- n이 홀수일 때의 계산법
public static double re_power(double x, int n) {
if(n==0) {
return 1;
}
else if ((n%2)==0) { // n이 짝수일 때
return re_power(x*x, n/2);
} else { // n이 홀수일 때
return x*re_power(x*x, (n-1)/2);
}
}두 함수를 main()에서 실행시켜보자.
public static void main(String[] args) {
double x = 2.0;
int n = 3;
System.out.println(for_power(x,n));
System.out.println(re_power(x, n));
}연산 결과는 둘다 8.0으로 잘 출력된다. 시간 복잡도를 통해 수행시간을 측정해볼 수 있다. 만약 n이 2의 제곱이라고 가정하면 문제의 크기가 다음과 같이 줄어든다.
시간 복잡도를 계산해보자.
이렇게 시간복잡도를 이용해서 계산하는 방법도 있지만, 가장 간단한 방법은 코드의 수행시간을 직접 측정해보는 것이다.
public static void main(String[] args) {
double x = 2.0;
int n = 3;
double beforeTime = System.currentTimeMillis(); // 코드 실행 전 시간 받아오기
//System.out.println(for_power(x,n));
System.out.println(re_power(x, n));
double afterTime = System.currentTimeMillis(); // 코드 실행 후 시간 받아오기
double secDiffTime = (afterTime - beforeTime)*0.001;
System.out.println("소요시간 : "+secDiffTime);
}피보나치 수열 프로그래밍
순환보다 반복이 효율적임을 보여주는 예시가 바로 '피보나치 수열 프로그래밍'이다. 피보나치 수열에 대한 설명은 다음 사이트를 참고하자.
피보나치 수열은 1,1,2,3,5,8,13,21,34,55.. 처럼 증가하는 규칙성을 파악할 수 있다.
재귀함수로 구현하기
public static int fib(int n) {
if (n == 0) {
return n;
} else if (n == 1) {
return 1;
} else {
return(fib(n-1) + fib(n-2));
}
}이를 main()에서 구현해보자.
public static void main(String[] args) {
System.out.println(fib(5));
}언뜻보면 아무런 문제가 없어보인다. 현재는 5를 구하는 것이지만, 구하고자 하는 숫자가 커지면 커질수록 메모리 속도가 기하급수적으로 느려진다. 계산을 못하는 것은 아니지만, 엄청난 시간이 소요되는 것이다.
위의 과정을 보면 알 수 있듯이, 5를 구하는 것인데도 비효율적으로 반복되는 함수들이 있다. 숫자가 커질수록 이렇게 의미없이 반복되는 함수들이 있어 호출이 몇 배로 증가하게 될 것이다.
반복문으로 구현하기 구현하기
public static void fib(int t) {
// 반복문을 이용한 피보나치수열
// f(n) = f(n-1) + f(n-2)
// 단 f(1) = 1 ,f(2) =2, 규칙은 f(3) 부터
int n = 0;
int n1 = 1;
int n2 = 1;
int n3 = 1;
for (n = 0; n < t; n++) {
if (n == 0 || n == 1) {
//System.out.println(1);
}else {
n1 = n2;
n2 = n3;
n3 = n1 + n2;
//System.out.println(n3);
}
}
System.out.println(n3);
}
public static void main(String[] args) {
fib(5);
}cf. C언어로 쉽게 풀어쓴 자료구조
