[Algorithm] 재귀(Recursion) 01
재귀
재귀란 무엇일까?
재귀의 사전적 의미를 보면 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻 한다.
재귀함수
그렇다면 재귀함수란 무엇일까?
간단하게 말하자면 자기 자신을 호출하는 함수이다.
사용조건
문제의 크기를 점점 작은 단위로 쪼갤 수 있어야 된다.
재귀 호출이 종료되는 시점이 있어야 된다. 만약, 종료되는 시점이 없다면 무한 루프에 빠지게 된다.
간단한 예제를 보자.
public class Test01 {
public static void main(String[] args){
func();
}
public static void func(){ // 자기 자신을 호출하는 함수. 즉, 재귀함수
System.out.println("Hello!");
func();
}
}위의 경우 재귀 호출이 종료되는 시점이 없기 때문에 "Hello!" 문자열이 무한으로 출력된다.
그렇다면 무한루프에 빠지지 않으려면 어떻게 해야 될까?
public class Test02 {
public static void main(String[] args){
int n = 4;
func(n);
}
public static void func(int k){
if (k<=0) // Base case
return;
else{ // Recursive case
System.out.println("Hello!");
func(k-1);
}
}
}바로 Base case 부분이 앞서 말한 재귀 호출이 종료되는 시점이다.
즉, recursion을 반복하다 보면 결국 base case로 수렴하게 된다.
재귀함수의 장점
그럼 재귀 메서드의 장점이 무엇일까?
바로 반복문을 여러 번 사용할 필요가 없어진다!
간단한 반복문이라면 굳이 재귀 메서드를 사용할 필요가 없지만 반복문이 많이 중첩된 상황이라면
말이 달라진다.
Ex)
for(int i= 0; i<10; i++){
for(int j= 0; j<10; j++){
for(int k= 0; k<10; k++){
for(int l= 0; l<10; l++){
for(int m= 0; m<10; m++){
someFunc(i, j, k, l, m);
}
}
}
}
}이런 경우에는 중첩된 반복문이 많아 반복문의 중첩 횟수(number of loops)를 예측하기 어렵다.
또한, 변수를 많이 사용해 프로그램 오류가 발생할 확률이 높다.
재귀함수의 단점
재귀 메서드에도 단점이 있다.
1. 코드를 직관적으로 알 수 없다.
2. 메서드를 반복하며 지역변수, 매개 변수, 반환값 모두 process stack에 저장된다.
즉, 반복문 보다 메모리를 더 많이 사용하게 된다.
3. 메서드를 호출하고 메서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생한다.
재귀함수의 간단한 예제
1 ~ n까지의 합
public class Test03 {
public static void main(String[] args) {
int result = func(4);
System.out.println(result);
}
public static int func(int n) {
if (n == 0) return 0; // n=0이라면 합은 0이다.
else
return n + func(n - 1); // n이 0보다 크다면 0ㅇ에서 n까지의 합은
// 0에서 n-1까지의 합에 n을 더한 것 이다.
}
}
Fectorial : n!
public class Test04 {
public static void main(String[] args) {
System.out.println(fectorial(5));
}
public static int fectorial(int n) {
if (n == 0)
return 1;
else
return n * fectorial(n - 1);
}
}
X^n
public class Test05 {
public static void main(String[] args) {
System.out.println(power(2, 3));
}
public static int power(int x, int n) {
if (n == 0) return 1;
else
return x * power(x, n - 1);
}
}
Fibonacci Number
public class Test06 {
public static void main(String[] args) {
System.out.println(fibonacci(6)); // 0 1 1 2 3 5 8
}
public static int fibonacci(int n) {
if (n < 2 ) return n;
else
return fibonacci(n-1) + fibonacci(n -2);
// 피보나치 수열의 n번 째 값은 (n-1) + (n-2)이다.
}
}
최대공약수: Euclid MeThod
public class Test07 {
public static void main(String[] args) {
System.out.println(gcd(2, 4));
}
public static int gcd(int m, int n) {
if (m < n) {
int tmp = m; m = n; n = tmp; // swap m and n
}
if (m % n == 0)
return n;
else
return gcd(n, m % n);
// m>=n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n)=n 이고,
// 그렇지 않으먄 gcd(m,n)= gcd(n, m%n)이다.
}
}좀 더 단순한 버전도 있다.
public class Test07_2 {
public static void main(String[] args) {
System.out.println(gcd(2, 4));
}
public static int gcd(int p, int q) {
if (q == 0)
return p;
else return gcd(q, p % q);
}
}