Recursion의 개념과 기본 예제들

1. Recursion 

- 순환 또는 재귀함수라고 부른다.

- 메소드를 정의할 때 자기 자신을 재참조 하는 방법을 말한다.

1) 무한루프가 발생하는 경우

: 아래의 코드는 func() 라는 메소드를 아무런 조건없이 다시 호출하여 무한루프에 빠지게 된다.

 public class RecursionTest {
	public static void main(String[] args) {
		func();
	}
	
	public static void func(){
		System.out.println("Hello");
		func();
	}
}

2) 조건을 추가해준 경우

: recursion이 항상 무한루프에 빠지는 것은 아니다.

 public class RecursionTest {
	public static void main(String[] args) {
		int n = 4;
		func(n);
	}
	
	public static void func(int k){
		if(k<=0)
			return; // base case
		else{
			System.out.println("Hello");
			func(k-1);  // recursive case
		}
		
	}
}

/*
<결과>
Hello
Hello
Hello
Hello
*/

3) 무한루프에 빠지지 않는 조건

① Base Case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. (위의 소스코드 if 문)

② Recursive Case: recursion을 반복하다보면 결국 Base Case로 수렴해야 한다.

4) Recursion의 해석 - 1~n 까지의 합 

 public class RecursionTest {
	public static void main(String[] args) {
		int result = func(4);
		System.out.println(result);
	}
	
	public static int func(int n){ // <- 이 함수는 0~n까지의 합을 구하는 것이다.
		if(n==0)
			return 0; // n=0이라면 합은 0이다.
		else{
			return n+func(n-1); // n이 0보다 크다면 0에서 n까지의 합은 0에서 n-1까지의 합에 n을 더한 것이다.
		}
		
	}
}

/*
<결과>
10
*/

5) Recursion을 이용하여 Factorial: n! 구하기

 public class RecursionTest {
	public static void main(String[] args) {
		int result = func(4);
		System.out.println(result);
	}
	
	public static int func(int n){
		if(n==0)
			return 1;
		else{
			return n*func(n-1);
		}
		
	}
}

6) Recursion을 이용하여 Fibonacci 구하기

 public class RecursionTest {
	public static void main(String[] args) {
		int result = func(6);
		System.out.println(result);
	}
	
	public static int func(int n){
		if(n<2)
			return n;
		else{
			return func(n-1)+func(n-2);
		}
		
	}
}

7) Recursion을 이용하여 최대공약수 구하기(유클리드 호제법)

- 유클리드 호제법: m≥n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n) = n이고, 그렇지 않으면 gcd(m,n) = gcd(n, m%n)이다.

 public class RecursionTest {
	public static void main(String[] args) {
		System.out.println((int) gcd(9,12));
	}
	
	public static double 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);
		
	}
}

더욱 간단한 코드

 public class RecursionTest {
	public static void main(String[] args) {
		System.out.println((int) gcd(9,12));
	}
	
	public static double gcd(int m, int n){
		
		if(n==0)
			return m;
		else
			return gcd(n, m%n);
	}
}