[Algorithm] 재귀(Recursion)란?

1. 재귀란?

어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라고 한다.

 

1.1 재귀 관련 용어

• 직접 재귀(direct recursion): 자신과 동일한 메서드를 호출하는 구조
• 간접 재귀(indirect recursion): 메서드 a가 메서드 b를 호출하고 다시 메서드 b가 메서드 a를 호출하는 구조
• 순수(genuinely) 재귀: 재귀 호출을 여러번 실행하는 메서드
• 꼬리 재귀(tail recursion): 재귀의 호출이 끝난 후 현재 함수에서 추가적인 연산을 요구하지 않도록 구현한 재귀 

1.2 재귀 사용시 유의 사항

• 재귀 함수는 반복적으로 호출된다. 하나의 함수의 실행이 끝나지 않았음에도 함수를 연속적으로 호출하기때문에 각각의 함수가 스택에 추가된다. 스택에는 함수의 변수, 반환값등이 저장된다. 이러한 과정은 반복문(interaton)에 비하여 메모리 사용량이 높고 속도의 저하가 발생할 수 있다. 
• 종료문이 올바르지 않으면 stackoverflow가 발생할 수 있다. 

1.3 꼬리 재귀(Tail Recursion)란?

재귀 함수는 자기 자신을 호출 한뒤 결과를 기다리는 동안 콜스택(call stack)의 부하가 발생한다. 따라서 메모리가 낭비된다는 문제가 있다.

 

꼬리 재귀를 이용하여 해당 부분을 최적화할 수 있다. 꼬리 재귀는 반환부(return문)에 연산이 없어야한다. 꼬리 최적화를 하면 컴파일러가 내부적으로 재귀 함수를 반복문으로 변경하여 실행하고, 스택도 한번만 호출한다. 

 

꼬리 재귀를 사용하기 전 컴파일러가 꼬리 최적화를 지원하는지 먼저 확인할 필요가 있다. 

// 일반 재귀
public int factorial(int n){
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

// 꼬리 재귀
public int factorialTail(int n, int acc){
  if(n == 1) return acc;
  return factorialTail(n - 1, acc * n);
}

public int factorial(int n){
  return factorialTail(n, 1);
}

 

2. 예제 

2.1 팩토리얼(factorial) 구하기

factorial 공식

public int factorial(int n) {
	return (n > 0) ? n * factorial(n-1) : 1; 
}

 

2.2. 두 정수의 최대 공약수(greatest common direct) 구하기

• 최대 공약수: 두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 때 나누어떨어지면 그 중에 작은 값
• 유클리드 호제법(Euclidean method of mutual division)

public int gcd(int x, int y) {
  if(y == 0) {
    return x;
  } else {
    return gcd(y, x % y);
  }
}

 

2.3. 하노이의 탑(towers of Hanoi)

이미지 출처: https://www.stemlittleexplorers.com/wp-content/uploads/2020/06/Tower-of-Hanoi-Tower-of-Brahma-or-Lucas-Tower.jpg

작은 원반이 위에, 큰 원반이 아래에 위치하도록 쌓은 원반을 3개의 기둥 사이에서 옮기는 문제이다. 모든 원반은 크기가 다르며 처음에는 모든 원반이 이 규칙에 맞게 첫번 째 기둥에 쌓여있다. 이 상태에서 모든 원반을 세번째 기둥으로 최소의 횟수로 옮기면 된다. 원반은 1개씩 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다.

// n는 원반의 개수, x는 시작 기둥의 번호, y는 목표 기둥의 번호

public void move(int n, int x, int y) {
  if(n > 1) {
    // 1. 바닥의 원반을 제외한 그룹을 시작 기둥에서 중간 기둥으로 옮김
    move(n - 1, x, 6 - x - y); 
  } 
  
  // 2. 바닥의 원반을 시작 기둥에서 목표 기둥으로 옮겼음을 출력
  System.out.printf("원반[%d]을 %d번 기둥에서 %d번 기둥으로 옮김\n", n, x, y);
  
  if(n > 1) {
    // 3. 바닥의 원반을 제외한 그룹을 중간 기둥에서 목표 기둥으로 옮김
    move(n - 1, 6 - x - y, y);
  }
}

기둥 번호의 합이 6(1+2+3)이므로 어느 기둥이건간에  6 - x - y으로 중간 기둥을 구할 수 있다.