얄팍한 코딩사전 - 재귀함수가 뭔가요? (Feat. 하노이의 탑)

Kkd·2024년 12월 2일

코딩 영상 후기

목록 보기

18/34

재귀 함수(Recursive Function)는 자기 자신을 호출하는 함수입니다. 주어진 문제를 더 작은 동일한 문제로 나누어 해결하는 방식으로 동작하며, 주로 분할 정복(Divide and Conquer) 방식의 문제 해결에 사용됩니다.

재귀 함수는 기본적으로 두 가지 구성 요소를 가집니다:
1. 기저 사례(Base Case): 재귀 호출이 더 이상 이루어지지 않고 종료되는 조건입니다. 이를 통해 무한 루프를 방지합니다.
2. 재귀 호출(Recursive Case): 문제를 더 작은 문제로 분할하여 자기 자신을 호출하는 부분입니다.

재귀 함수는 문제를 더 작은 문제로 나누어 해결하는 방식으로 매우 유용하지만, 그 사용에는 장점과 단점이 존재합니다. 이를 잘 이해하고 적절히 활용하는 것이 중요합니다.

재귀 함수의 장점

변수를 여럿 만들 필요가 없다
- 재귀 함수는 상태를 매개변수나 반환값을 통해 전달할 수 있기 때문에, 반복문에서처럼 여러 개의 임시 변수를 만들 필요가 없습니다. 예를 들어, 문제의 상태를 저장하고 변경할 때, tmp와 같은 변수를 사용하기보다는 재귀 호출을 통해 자연스럽게 상태가 전달됩니다. 이를 통해 코드가 간결하고 직관적으로 작성될 수 있습니다.
반복문 없이 간결한 코드 작성
- 재귀 함수는 while이나 for와 같은 반복문을 사용하지 않고 문제를 해결할 수 있기 때문에 코드가 간결하고 읽기 쉬운 구조가 됩니다. 특히 분할 정복 방식의 문제 해결에서 재귀는 매우 유용하게 작동합니다. 예를 들어, 하노이의 탑이나 트리 탐색과 같은 문제는 재귀적 접근이 자연스럽고 직관적입니다.

재귀 함수의 단점

메모리 사용 증가
- 재귀 함수는 함수 호출이 반복될 때마다 매개변수, 지역 변수, 반환값 등을 프로세스 스택에 저장해야 합니다. 이 과정에서 스택 오버플로우가 발생할 수 있으며, 메모리 소비가 많아져 성능 저하를 초래할 수 있습니다. 반복문을 사용할 때보다 메모리 사용량이 급격히 늘어나므로, 재귀 호출의 깊이가 깊어질수록 메모리 비용이 커질 수 있습니다.
컨텍스트 스위칭 비용
- 재귀 함수는 함수 호출과 복귀를 반복하는 과정에서 컨텍스트 스위칭이 발생합니다. 즉, 각 호출마다 새로운 매개변수, 변수 값 등을 저장하고 복원하는 과정이 필요하기 때문에, 이로 인해 시간 비용이 발생할 수 있습니다. 반복문에서는 이러한 과정 없이 순차적으로 처리되므로, 재귀에 비해 더 빠를 수 있습니다.

하노이의 탑 문제

하노이의 탑은 고전적인 재귀 문제 중 하나로, 세 개의 기둥과 여러 개의 원판을 사용하여 한 기둥에서 다른 기둥으로 원판을 옮기는 문제입니다. 원판을 옮기는 규칙은 다음과 같습니다:

한 번에 한 개의 원판만 옮길 수 있다.
원판은 작은 것이 큰 것 위에 놓을 수 없다.
세 개의 기둥 중 하나는 비어 있어야 한다.

이 문제는 재귀로 해결할 수 있으며, 각 단계에서 문제를 더 작은 하위 문제로 나누어 해결합니다.

하노이의 탑 재귀 풀이

하노이의 탑을 풀기 위한 재귀 함수는 다음과 같은 절차를 따릅니다:

기저 사례: 만약 원판이 1개라면, 단순히 원판을 목적지 기둥으로 옮깁니다.
재귀 호출:
- n개의 원판이 있을 때, 상위 n-1개의 원판을 보조 기둥으로 옮깁니다.
- 남은 1개의 원판을 목표 기둥으로 옮깁니다.
- 보조 기둥에 있던 n-1개의 원판을 목표 기둥으로 옮깁니다.

하노이의 탑 예시 코드 (Java)

public class Hanoi {
    public static void main(String[] args) {
        int n = 3; // 원판 개수
        moveTower(n, 'A', 'C', 'B'); // A -> C, B는 보조 기둥
    }

    // 하노이의 탑 함수
    public static void moveTower(int n, char from, char to, char aux) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + from + " to " + to);
        } else {
            // (1) n-1개의 원판을 보조 기둥으로 옮깁니다.
            moveTower(n - 1, from, aux, to);
            // (2) n번째 원판을 목표 기둥으로 옮깁니다.
            System.out.println("Move disk " + n + " from " + from + " to " + to);
            // (3) 보조 기둥에 있던 n-1개의 원판을 목표 기둥으로 옮깁니다.
            moveTower(n - 1, aux, to, from);
        }
    }
}

동작 설명

moveTower(n, from, to, aux) 함수는 n개의 원판을 from 기둥에서 to 기둥으로 옮기는데, aux는 보조 기둥입니다.
기저 사례: n == 1일 때는 원판을 바로 옮깁니다.
재귀 호출: n > 1일 때는 먼저 n-1개의 원판을 보조 기둥으로 옮기고, 가장 큰 원판을 목표 기둥으로 옮긴 후, 다시 보조 기둥에 있던 원판들을 목표 기둥으로 옮깁니다.

하노이의 탑 재귀 풀이의 중요성

문제를 더 작은 하위 문제로 나누는 방식: n개의 원판을 이동하는 문제를 n-1개의 원판을 이동하는 문제로 나누는 방식으로 해결합니다.
기저 사례를 명확하게 정의하여 종료 조건을 마련하고, 그 외의 경우에는 재귀적으로 문제를 분할하여 해결합니다.

재귀 함수의 특징

자기 자신을 호출: 문제를 더 작은 문제로 나누어 해결합니다.
기저 사례를 설정하여 무한 재귀 호출을 방지합니다.
간결한 코드: 재귀 함수는 명확한 문제 해결 절차를 따르므로, 코드를 간결하고 직관적으로 작성할 수 있습니다.

결론

재귀 함수는 문제를 간결하고 직관적으로 해결할 수 있는 유용한 도구입니다. 하지만 과도한 재귀 호출은 메모리 사용과 성능 저하를 일으킬 수 있으므로, 재귀와 반복문을 적절히 선택하여 사용하는 것이 중요합니다. 문제의 특성에 맞는 방법을 선택하는 것이 성능을 최적화하는 데 도움이 됩니다.

추가 학습 자료