[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);
    }
}