재귀

• 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다.
• 재귀는 병합 정렬과 퀵 정렬, 이진검색트리 등에 사용된다.
• 재귀의 사용 예로 양의 정수의 팩토리얼 (n!)을 들 수 있다. 예를 들어 10의 팩토리얼인 10!은 10 * 9!로 구할 수 있고 그 우변에서 사용되는 식 9!은 9 * 8!로 구할 수 있다.
• 메서드가 자신을 다시 호출하는 방식을 재귀 호출(recursive call)이라고 한다.
• 직접 재귀 : 자신과 같은 메서드를 내부에서 다시 호출하는 것
• 간접 재귀 : 다른 메서드를 통해 자기 자신과 같은 메서드를 호출하는 것
  • a()에서 b() 호출 → b()에서 a() 호출 → a()에서 b() 호출

//팩토리얼을 재귀적으로 구현
public class Factorial {
 
    //양의 정수 n의 팩토리얼을 반환한다
    static int factorical(int n) {
        if (n > 0)
            return n * factorical(n - 1);
        else 
            return 1;
    }
}

 

유클리드 호제법

• 두 정수의 최대공약수를 구하기 위해 유클리드 호제법(Euclidean method of mutual division) 알고리즘을 이용하여 재귀적으로 구할 수 있다.
• 두 정수를 직사각형의 두 변의 길이라고 생각했을 때 정사각형으로 완전히 채울 수 있을 때까지 반복하고 정사각형만으로 구성되었을 때의 변의 길이가 최대공약수가 된다.
  • 22 * 8 크기의 직사각형 → 8 * 8 정사각형 2개로 채움
  • 남은 8 * 6 크기의 직사각형 → 6 * 6 정사각형 1개로 채움
  • 남은 6 * 2 크기의 직사각형 → 2 * 2 정사각형 3개로 다 채움 → 2가 최대공약수가 됨
• 즉 두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 때 나누어떨어지는 가장 작은 값이 최대공약수가 된다. 나누어지지 않으면 작은 값에 대해 나누어떨어질 때까지 같은 과정을 재귀적으로 반복한다.

//유클리드 호제법으로 최대공약수 구하기
public class EuclidGCD {
 
    //정수의 x, y의 최대공약수를 구하여 반환한다
    static int gcd(int x, int y) {
        if (y == 0)
            return x;
        else
            return gcd(y , x % y);
    }
}

 

재귀 알고리즘의 비재귀적 표현

static void recur(int n) {
    if (n > 0) {
        recur(n - 1);
        System.out.println(n);
        recur(n - 2);
    }
}

• recur(n-1)의 수행이 먼저 끝나야 n의 값을 출력할 수 있기 때문에 현재 n의 값을 잠시 저장하고 저장했던 값을 다시 꺼내 출력하기 위해 스택을 이용한다.

//비재귀적 표현
static void recur(int n) {
    IntStack stack = new IntStack(n);
    
    while (true) {
        if (n > 0) {
            stack.push(n);
            n -= 1;
            continue;
        }
        if (stack.isEmpty() != true) {
            n = stack.pop();
            System.out.println(n);
            n -= 2;
            continue;
        }
        break;
    }
}