5. 재귀 - bloodfinger8/AlgorithmStudy GitHub Wiki

재귀의 기본

재귀랑, 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 recursive라고 한다.

factorial을 구하는 재귀 기본 예제

int factorial(int n) {
  if(n > 0) { // 종료 조건
    return n * factorial(n-1); // 자기 자신을 호출
  } else {
    return 1;
  }
}

유클리드 호제법을 이용한 두 정수의 최대 공약수 구하기

  • 유클리드 호제법이란, 두 정수를 직사각형의 두 변의 길이라고 생각하면 된다.
  • 먼저 길이가 더 긴 수를 작은 수로 나눈 나머지를 구한다.
  • 만약 두 수가 나누어 떨어지면 작은수가 최대 공약수이다.
  • 나누어 떨어지지 않으면 작은수와 나머지수를 인자로 재귀 호출을 수행한다.

아래는 위 유클리드 호제법을 기반으로 코드로 구현한 내용이다.

int 최대공약수(int x, int y) {
        int a;
        if(x > y) {
            a = x % y;
        } else {
            a = y % x;
        }
        if(a == 0) return y;
        else return 최대공약수(Math.min(x, y), a);
    }

재귀 알고리즘의 분석

하향식 분석

코드 예시

public void recur(int n) {
        if(n > 0) {
            recur(n-1);
            System.out.println(n);
            recur(n-2);
        }
    }
  • 가장 위쪽에 위치한 트리 내 상자의 함수 호출부터 시작해 계단식으로 자세히 조사해가는 분석 기법.
1) recur(3)을 실행
2) 4를 출력 // 바로 출력 불가. recur(3)의 실행이 완료된 다음에 출력 가능. 그전까지 계속 트리의 왼쪽 화살표를 따라감.
3) recur(2)를 실행
  • 트리의 꼭대기부터 분석하면 같은 함수의 호출이 여러 번 나올 수 있기 때문에 하향힉 분석이 반드시 효율적이라고 말할 수 없다.

상향식 분석

  • 위쪽부터 분석하는 하향식 분석과는 대조적으로 아래쪽부터 쌓아올리며 분석하는 방법이 상향식 분석이다.
  • recur 함수는 n이 양수일 때만 실행하므로 먼저 recur(1)을 생각한다.

수행 과정

// 1단계
1) recur(0)을 실행 -> 출력할 내용 없음!
2) 1을 출력 -> 출력
3) recur(-1)을 실행 -> 출력할 내용 없음!

// 2단계
1) recur(1)을 실행 -> 1 출력
2) 2를 출력 -> 2 출력 
3) recur(0)을 실행 -> 출력할 내용 없음!

...
...

하노이의 탑

  • 쌓아 놓은 원반을 최소의 횟수로 옮기기 위한 알고리즘
  • 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이엥서 옮기는 문제
  • 모든 원반은 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥이 쌓여있다.
  • 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮겨야 한다.
  • 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다.

코드 구현

하노이의탑(3,1,3);


public static void 하노이의탑(int n, int 시작기둥, int 목표기둥) {
        if(n > 1) {
            하노이의탑(n-1, 시작기둥, 6 - 시작기둥 - 목표기둥); // 그룹을 시작 기둥에서 중간 기둥으로
            // 6 - 시작기둥 - 목표기둥 = 기둥번호합 - 나머지 기둥들 => 중간기둥
        }
        System.out.println(String.format("원반[%d]를 %d 기둥에서 %d로 옮김", n, 시작기둥, 목표기둥));
        if(n > 1) {
            하노이의탑(n-1, 6 - 시작기둥 - 목표기둥, 목표기둥); // 그룹을 둥간 기둥에서 목표 기둥으로
        }
    }

재귀 알고리즘 문제 풀기

예상 면접 질문