22. Recursion

재귀(Recursion)는 재귀호출을 이용하여 문제를 해결하는 것이다. 재귀호출은 함수 내에서 자신을 다시 호출하는 것이며, 이러한 함수를 재귀함수라고 한다. 이것은 보통 문제에 주어진 상황으로부터 점화식을 유도할 수 있는 경우에 사용되는 방법이다. 물론 DFS같이 재귀함수가 등장하지만 이 유형으로 보기 어려운 것들도 있다.

 

재귀 문제를 풀 때는 먼저 주어진 상황을 어떻게 점화식으로 나타낼 수 있는지 구성하고, 그것을 바탕으로 재귀함수를 작성한다. 반복문 안에서 재귀호출이 발생할 수도 있다.

 

재귀함수에는 기저 사례(Base Case)를 처리하는 부분이 있어야 한다. 기저 사례는 재귀함수에서 나타날 수 있는 가장 기본적인 경우로 더이상 재귀호출을 할 수 없거나 재귀호출 없이 바로 처리할 수 있는 경우를 의미한다.

 

재귀로 풀 수 있는 문제의 가장 대표적인 예시인 피보나치 수를 통해서 개념을 정리하자.

 

피보나치 수를 다음과 같이 정의할 수 있음은 잘 알려져 있다.

f(0) = 1
f(1) = 1
f(n) = f(n-2) + f(n-1) (n >= 2)

따라서 이것을 그대로 구현하면 다음과 같이 된다. ($n$이 음수인 경우나 함수값이 너무 커서 오버플로우가 나는 경우는 생각하지 않는다.)

int f(int n)
{
    if(n < 2)return 1;
    return f(n-2) + f(n-1);
}

여기서 기저 사례는 $n$이 $0, 1$일 때가 된다. 이때는 재귀호출 없이 바로 함수값을 반환하고, $n$이 $1$보다 크다면 재귀호출을 통해서 함수값을 구한다.

 

또한 위 코드의 문제점은 $n$이 조금만 커져도 성능이 급격하게 떨어진다는 것이다. 이 문제를 해결할 수 있는 것이 나중 글에서 설명할 메모이제이션이다. 중복되는 부분 문제가 많다면 메모이제이션을 통해서 재귀호출의 횟수를 크게 줄일 수 있다. 여기서부터는 동적 계획법의 영역이므로 자세한 설명은 생략한다.

 

[연습문제]

 

BOJ 2630. 색종이 만들기 (Silver III)

전체 영역이 같은 색일 경우 그 색 색종이의 수에 $1$을 더하고, 그렇지 않다면 색종이를 네 부분으로 나눈 뒤 각각의 부분을 확인하는 것을 반복한다.

여담으로 이 문제는 백준 사이트에서 실수로 삭제되었다가 복구된 적이 있다. 당시 solved.ac에서는 투표 DB에 문제 ID를 참조하는 Foreign Key를 쓰고 있었는데 문제가 삭제되면서 문제에 쌓인 난이도 투표도 다 날아가 버렸고, 백업 데이터가 없어서 날아간 투표 내역을 복구할 수 없게 되었다. 당시에 이 문제를 푼 사람은 $15000$명 정도였는데 이중 solved.ac를 사용하는 사람들의 문제 해결 기록도 다 날아가 버렸다. 그리고 이 문제가 Class $3$ Essential에 있었는데 여기서도 문제 하나가 빠지면서 일부 사용자들의 Class 기록이 변하는 문제도 생겼다. 결국 solved.ac DB의 Foreign Key가 사라지는 방향으로 패치되는 계기가 되었다고 한다.

 

BOJ 11729. 하노이 탑 이동 순서 (Silver II)

$1$번 원판부터 $n$번 원판까지를 기둥 $1$에서 기둥 $3$으로 옮기는 것을 다음 세 단계로 나눌 수 있다.

• $1\text{~}(n-1)$번 원판을 기둥 $1$에서 기둥 $2$로 옮긴다.
• $n$번 원판을 기둥 $1$에서 기둥 $3$으로 옮긴다.
• $1\text{~}(n-1)$번 원판을 기둥 $2$에서 기둥 $3$으로 옮긴다.

이렇게 문제를 나누면 재귀호출로 간단하게 문제를 풀 수 있다. 중간에는 옮기는 기둥, 옮길 기둥이 바뀌기도 하므로 그것도 재귀함수의 인자로 넘기면 된다.

 

→ solved.ac tag: recursion