Recursion의 개념과 기본 예제들 1

Recursion은 순환이라고 부르기도하고 재귀함수라고 부르기도 한다.

 

자기 자신을 호출하는 함수 func()이다.

void func()

{

    func();

}

어떤 함수가 자기 자신을 호출하면 어떻게 될까?

public static void func() {
	System.out.println("Hello")
    func();
 }

무한 루프에 빠지게 되는 것이 당연하다.

 

public static void func(int k){
	if(k <=0 )
    	return;
    else{
    	System.out.println("Hello");
        func(k-1);
        }
}

 

if문을 사용하여 탈출할 경우를 만들어주고 

호출할때 k-1을 넘겨주어 감소시켜준다면 멈출 수 있게 만들 수도 있다.

 

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

 

---

 

무한 루프에 빠지지 않기 위해선?

 

적어도 하나의 다시 돌아가지 않아야 하는 경우가 존재해야한다.

이것을 Base case라고 부른다. 위의 코드의 if문이 Base case이다.

 

그렇다고 해서 종료 될 수 있을까?

 

단순히 Base case가 존재하므로 인해 종료 되는 것은 아니고

모든 경우들은 반복하다보면 base case로 수렴해야한다는 조건이다.

 

총 2가지의 조건이 만족되면 무한 루프에 빠지지 않는 recursion을 구현 할 수 있다.

 

---

public static int func(int n) {
	if(n==0)
    	return 0;
    else
    	return n + func(n-1);
}

1~n까지의 합을 recursion을 이용하여 쉽게 구현할 수 있다.

 

public static double gcd(int m, int n){
	if(m<n) {
    	int tmp=m;
        m=n;
        n=tmp;
    }
    if(m%n==0)
    	return n;
    else
    	return gcd(n, m%n);
}

정수론 시간에 배웠던 

최대공약수를 구하는 알고리즘인 유클리드 알고리즘이다.

 

첫번째 if문은 m이 더 큰수가 되도록 바꾸는 로직이고

두번째 if문은 m이 n으로 나누어떨어진다면 n을 리턴하고

그렇지 않다면 인자값을 n, m%n을 주며 재귀호출한다.

 

public static int gcd(int p, int q){
	if(q==0)
    	return p;
    else
    	return gcd(q,p%q);
}

이 코드는 좀더 단순한 유클리드 알고리즘이다.