재귀 알고리즘(recursive - algorithm)

이종훈·2025년 7월 10일

Alghorithm

개발 일지

목록 보기

18/21

재귀(Recursion)란?

재귀란 자기 자신을 호출하는 것을 말하며, 이를 적용한 재귀 알고리즘은 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘을 말합니다.

재귀 함수

재귀 함수는 자기 자신을 호출하는 함수로, 일반적으로 다음 2가지 조건을 반드시 만족해야합니다.

1: 종료 조건

재귀 함수는 특정 조건에 도달하면 더 이상 자기 자신을 호출하지 않고 함수 실행을 종료하는 종료 조건을 반드시 포함해야합니다. 이러한 종료 조건이 없다면 함수가 무한히 호출되어 프로그램이 오버플로우에 걸리거나 비정상적으로 종료하게 됩니다.

2: 재귀 호출

또한 재귀 함수는 자기 자신을 반드시 호출해야하며, 이는 재귀를 만족하기 위해 당연히 포함되어야 하는 조건입니다. 이때 자기 자신을 호출하는 과정에서 매개변수나 값의 상태가 점점 종료 조건에 가까워지도록 구현되어야합니다.

예시 1

public void func(int count) {
    if (count == 5) { // 1: 종료 조건
        return;
    }
    System.out.println("1");
    func(count + 1); // 2: 재귀 호출
    System.out.println("2");
}

위 코드에서 func(0)을 실행하면 출력 결과가 어떻게 될까요?

우선 func(0)을 호출하면 1이 출력되고 func(2)가 호출됩니다. func(2)는 마찬가지로 1을 출력하고 func(3)을 호출합니다. 이 과정은 count가 5가 되는 func(5) 호출까지 반복됩니다. func(5)가 호출되면 count는 5가 되어 return 되고, 이와 동시에 func(5)는 바로 종료됩니다.
그 후, 각 func(4~0)의 func(count + 1) 호출 다음 코드인 2 출력 코드가 실행되어 2가 총 5번 출력됩니다.

따라서 func(0)의 출력 결과는 1111122222가 됩니다.

이러한 실행 흐름을 "후위 순회"라고 합니다. 후위 순회는 재귀 호출 이후의 코드가 복구할 때 실행되는 흐름을 말합니다. 즉, 재귀 호출은 마치 깊이 우선 탐색(DFS)처럼 끝까지 들어갔다가 돌아오면서 남은 코드를 실행하는 구조라고 생각하면 됩니다.

예시 2(피보나치 수열)

또 다른 재귀 함수의 대표적인 예시로 피보나치 수열이 있습니다.

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

위 코드에서 fibonacci(4)를 실행하면 fibonacci(2) + fibonacci(3)이 return 됩니다. 그리고 각 2와 3은 0 + 1, 1 + 2를 반환하게 되고, 0과 1은 2보다 작기 때문에 각각의 값인 0과 1이 매핑됩니다. 따라서 0 과 1의 합인 fibonacci(2)는 1이 되고, 1과 2의 합인 fibonacci(3)은 1가 됩니다. 그리고 둘의 합인 fibonacci(4)는 3이 되며 코드는 종료됩니다.

하지만 위 코드에서 같은 값이 여러 번 중복 계산 된다는 문제점이 있습니다. fibonacci(4) 실행 시 2와 3이 return되어 각 2와 3이 0, 1과 1, 2를 반환하는데 이때 1과 2가 중복 호출되어 계산됩니다. 이처럼 재귀 호출 시 중복 계산되는 경우에는 어떻게 수정해야할까요?

재귀 함수는 언제 사용해야할까?

재귀 함수는 문제를 더 작은 동일한 구조의 문제로 분할한다는 점에서 효율적입니다. 또한 재귀 함수의 경우 자기 자신을 간단히 호출함으로서 반복문보다 코드가 훨씬 간결하여 효율성 면에서도 좋습니다.

하지만 모든 문제에 재귀가 적합한 것은 아닙니다. 상단의 피보나치 예제처럼 같은 함수가 반복적으로 호출되는 경우에는 단순 재귀 방식은 비효율적입니다. 재귀 함수는 트리 구조 탐색, 하노이의 탑, 백트래킹, DFS 등에서 반복문으로는 구현이 복잡하고, 반복 횟수를 예측하기 어려운 경우 사용하는 것이 좋습니다.

동적 프로그래밍(DP)

추가적으로 재귀 함수로 구현 시 동일한 함수가 반복적으로 호출되어 비효율적인 피보나치 수열 문제는 DP(동적 프로그래밍) 방식으로 구현하는 것이 효율적입니다. 동적 프로그래밍은 이미 계산한 값을 저장해 두었다가 같은 값이 필요할 때 재사용하는 방식으로 중복 계산을 방지할 수 있습니다.

int[] memo = new int[100];
int fibonacci(int n) {
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
}

상단의 코드는 DP 방식으로 구현한 피보나치 수열 문제입니다. 이를 통해 중복 계산을 방지하면서 재귀 함수를 호출하여 보다 효율적으로 구현할 수 있고, 시간 복잡도 또한 O(2^n)에서 O(n)으로 크게 줄일 수 있습니다.