[알고리즘] 재귀(Recursion)와 백트래킹(Backtracking)

이 글은 재귀(recursion)와 백트래킹(backtracking)에 대해 정리한 글입니다.

---

재귀 함수 (Recursion Function)

재귀 함수는 복잡한 문제를 단순화해서 생각할 때 유용하며, 특히 분할 정복, 트리/그래프 탐색(DFS). 백트래킹 등 다양한 알고리즘 설계 기법에서 매우 중요한 역할을 한다. 직관적으로 이해하기에는 어려움이 있으나, 디버깅을 통해 재귀 함수가 동작하는 과정을 이해하면 알고리즘 설계에 있어서 도움이 된다

재귀란?

정의

• 어떤 함수가 자기 자신을 다시 호출하여 문제를 해결하는 프로그래밍 기법을 의미
• 문제를 풀기 위해 문제의 부분 문제를 재귀적으로 해결하고, 그 해를 이용하여 전체 문제의 해를 구하는 구조를 가짐

재귀의 기본 구조

재귀 함수를 작성할 때에는 기저 조건(base case)과 재귀 호출(recursive case)을 핵심적으로 고려해야 한다.

재귀 함수가 동작하는 과정에서 기저 조건(base case)이 설정되지 않으면 무한 재귀에 빠질 수 있으므로, 반드시 기저 조건을 작성하는 것이 중요하다.

기저 조건 (base case)

• 재귀 호출이 더 이상 진행되지 않아야 할 조건 (재귀 함수를 탈출(return)하는 조건)
  • ex. 팩토리얼에서 n = 0 또는 n = 1일 때 1을 반환하면 재귀가 멈춤

재귀 호출 (recursive case)

• 전체 문제를 더 작은 하위 문제로 나누고, 그 하위 문제를 스스로 호출하여 해결
  • ex. n! = n * (n - 1)!에서, factorial(n-1) 호출

재귀 호출의 실제 동작 (콜 스택, Call Stack)

• 콜 스택 (함수 호출 스택) 위에 함수들이 순서대로 쌓이고, 호출이 완료되면 해당 함수가 스택에서 제거되며 호출 직전의 함수로 복귀
• 재귀가 깊어질수록 스택에 많은 함수 호출 정보가 쌓이므로, 지나치게 깊은 재귀는 스택 오버플로(stack overflow)를 발생시킬 수 있음

// 팩토리얼의 계산 과정 (n = 4 일 때)
factorial(4)
 └─> factorial(3)
      └─> factorial(2)
           └─> factorial(1)
                └─> factorial(0)  // base case → 1 반환
                └─> factorial(1) 결과 = 1 * factorial(0) = 1
           └─> factorial(2) 결과 = 2 * factorial(1) = 2
      └─> factorial(3) 결과 = 3 * factorial(2) = 6
 └─> factorial(4) 결과 = 4 * factorial(3) = 24

재귀 함수의 기본 구조

#include <iostream>
using namespace std;

void func(int now) {
  // 기저 조건 (base case)
  if (now == 4) {
    cout << now << " ";
    return;
  }
  // 재귀 조건 (recursive case)
  cout << now << " ";
  func(now + 1);
  cout << now << " ";
}

int main() {
  func(0);
  return 0;
}

• 기본 구조를 확실하게 익힌 후, 함수가 다시 돌아온다는 개념을 이해해야 함
  • Tip! 코드를 작성하고 디버깅을 하며 now의 값이 어떻게 변하는지 확인해볼 것!

재귀 함수의 호출과 반환을 시각적으로 표현한 다이어그램

재귀 함수 이해 Tip!
재귀 함수의 동작 과정을 이해할 때에는 함수가 호출되고 다시 돌아온다는 개념을 반드시 이해해야 한다. 0부터 5까지 커졌다가 다시 0으로 돌아오는 코드를 반복문이 아닌 재귀 함수를 통해 만들어보고 디버깅을 통해 콜 스택이 변화함에 따라 변수의 값이 어떻게 달라지는 지 확인하는 과정을 거치면 이해하는 데 도움이 된다.

재귀의 대표 예시

팩토리얼 (Factorial) 

• n이 자연수일 때, 1부터 n까지의 모든 양의 정수(자연수)의 곱

// C++
#include <iostream>
using namespace std;

long long factorial(int n) {
    if (n <= 1) {
        return 1;  // base case
    }
    return (long long)n * factorial(n - 1); // recursive case
}

int main(){
    int n = 5;
    cout << n << "! = " << factorial(n) << endl; // 120
    return 0;
}

피보나치 수열 (Fibonacci)

• 각 숫자가 이전 두 숫자의 합으로 이루어진 수열
• 단, n = 0의 값은 0, n = 1의 값은 1
  • ex. 0, 1, 1, 2, 3, 5, 8, ...

// C++
long long fib(int n) {
    if (n <= 1) {
        return n; // 0 또는 1 그대로 반환
    }
    return fib(n - 1) + fib(n - 2);
}

유클리드 호제법 (최대공약수, GCD)

• 두 수 a와 b( 단, $ a \ge b $ )에 대해서 GCD(a, b) = GCD(b, a % b)
• 단, b = 0이면 a가 최대공약수

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

재귀 함수의 장단점

재귀 함수의 장점

• 코드 가독성 : 논리적으로 간결하고, 수학적 정의와 유사한 형식으로 직관적
• 문제 분할에 용이 : 트리나 그래프 등 복잡한 자료 구조 탐색에 적합
• 분할 정복(ex. 퀵 정렬, 병합 정렬) 구현이 직관적

재귀 함수의 단점

• 성능 오버헤드 : 함수 호출에 따른 스택 사용, 매 호출 시 인자 복사, 리턴 주소 저장 등
• 스택 오버플로 위험 : 너무 깊은 재귀 시 발생 가능
• 과도한 중복 연산 : 피보나치 수열과 같이 같은 결과를 여러 번 계산할 수 있음
• 꼭 재귀가 아니여도 반복으로 해결 가능할 때가 많음 (반복문이 성능 면에서 유리할 수 있음)

재귀 함수 작성 시 주의점

• 기저 조건(base case)을 반드시 명시
  • 재귀가 끝나지 않고 무한 루프에 빠질 수 있음
• 재귀 깊이(Depth) 확인
  • 입력 범위가 커질 수 있는 문제에서는 재귀 깊이가 너무 깊어지지 않도록 주의
  • 필요하다면 꼬리 재귀 최적화, 반복문 변환 등을 검토
• 중복 계산
  • 피보나치 수열과 같은 케이스에서는 메모이제이션이나 DP 등을 적용
• 디버깅의 어려움
  • 단계를 추적하기 위해 (ex. 디버거 사용, 중간 출력 등) 별도의 주의 필요

재귀 핵심 요약

• 재귀(recursion)는 함수가 자기 자신을 호출함으로써 하위 문제를 해결하고, 이를 합쳐 최종 문제를 해결하는 방식
• 기본적으로 기저 조건(base case)과 재귀적 호출(재귀 단계)로 구성되며, 콜 스택(call stack)을 통해 구현
• 일부 문제에서는 재귀가 매우 간단하고 직관적인 표현을 가능하게 하지만, 성능과 메모리 측면에서 주의가 필요

---

백트래킹 (Backtracking)

백트래킹의 개념

정의

• 해를 찾기 위해 가능한 모든 경우를 시도하지만, 불가능하다고 판단되면 되돌아가서 다른 경우를 탐색하는 기법
• 재귀 기반으로, 어떤 단계에서 해가 될 수 없거나(유망하지 않으면) 더 이상 진행하지 않고 초기에 탐색을 중단(가지치기, prunning)함으로써, 불필요한 연산을 줄이는 것이 핵심

주요 개념

• 모든 경우를 생성하는 재귀적 방법
• 중간에 조건을 위배하거나 목표에 부합하지 않음이 명확해지면, 해당 경로는 더 이상 진행하지 않고 포기
• 가능성이 있는 경로만 계속 진행하여 최종 해(또는 모든 해)를 찾음

동작 원리와 단계

• 상태 정의
  • 지금까지 어떤 선택을 했는지를 표현하는 방법
• 재귀 함수 정의
  • func(int level); 혹은 backtrack(step, ... ); 등으로 정의
  • 현재 단계(노드)에서 다음 선택을 시도하고 각각에 대해 재귀 호출
• 가지치지 조건 체크
  • 현재 상태가 유효한지 (제약 조건을 만족하는지)
  • 더 이상 해가 될 수 없는지 (ex. 목표 해를 초과하였는지, 충돌이 있는지 등)
  • 불가능하다고 판단되면, 재귀 호출을 중단하고 돌아감
• 결과 처리
  • 해를 하나 찾았다면 기록하거나, 모든 해를 찾으면 종료하는 등 문제 요구에 맞춰 결과 처리
• 백트래킹 처리
  • 재귀 함수에서 나온 뒤, 다른 선택지를 시도하기 위해 직전 상태로 복원

기본 코드 구조

가장 전형적인 백트래킹 구조를 사용하여 입력된 배열의 모든 순열을 생성하는 코드는 다음과 같다.

C++ 코드

#include <iostream>
#include <vector>
using namespace std;

// 전역 변수 예시 (실무에서는 필요에 따라 함수 내부로 옮길 수 있음)
vector<int> arr;    // 순열을 만들 원소가 담긴 배열
vector<bool> used;  // 해당 원소를 사용했는지 여부
vector<int> perm;   // 현재까지 만든 순열(부분 결과)

// depth: 현재까지 선택한 원소의 개수(깊이)
// n: 배열 원소의 총 개수
void backtrack(int depth, int n) {
  // 1. 종료 조건: depth가 n에 도달하면 순열이 완성되었음을 의미
  if (depth == n) {
    // 완성된 순열 출력
    for (int num : perm) {
      cout << num << " ";
    }
    cout << "\n";
    return;
  }

  // 2. 백트래킹 탐색
  for (int i = 0; i < n; i++) {
    if (used[i]) continue;  // 사용한 원소면 넘기기
    used[i] = true;         // 사용 처리
    perm.push_back(arr[i]);

    // 다음 위치로 이동
    backtrack(depth + 1, n);

    // 되돌리기(Backtrack): 상태 복원
    perm.pop_back();
    used[i] = false;
  }
}

int main() {
  // 예시: {1, 2, 3} 배열의 순열을 구해보자.
  arr = {1, 2, 3};
  int n = arr.size();

  // used 배열 초기화
  used.assign(n, false);

  // 백트래킹 시작
  backtrack(0, n);

  return 0;
}

• backtrack(depth, n)
  • depth == n이면, perm에 들어있는 원소가 하나의 완성된 순열이므로 출력 후 반환
  • 그렇지 않다면, 아직 사용하지 않은 다른 원소를 찾음
• 사용 처리 및 탐색
  • used[i] = true 및 perm.push_back(arr[i])로 현재 i번째 원소를 순열에 넣은 뒤, depth + 1 단계로 재귀 호출
• 되돌리기 (backtrack)
  • 재귀 호출이 끝난 뒤에는 perm.pop_back()와 used[i] = false로 원상태로 복구

Python 코드

# 순열을 만들 원소
arr = [1, 2, 3]

# 각종 전역 변수
n = len(arr)
used = [False] * n   # 해당 원소를 사용했는지 여부
perm = []            # 현재까지 만든 순열(부분 결과)

def backtrack(depth):
    # 1. 종료 조건: depth가 n에 도달하면 순열 완성
    if depth == n:
        # 완성된 순열 출력
        print(perm)
        return
    
    # 2. 백트래킹 탐색
    for i in range(n):
        # 아직 사용되지 않은 원소를 선택
        if not used[i]:
            used[i] = True
            perm.append(arr[i])

            # 다음 단계로 이동
            backtrack(depth + 1)

            # 되돌리기(Backtrack): 상태 복원
            perm.pop()
            used[i] = False

# 백트래킹 시작
backtrack(0)

• backtrack(depth)
  • depth == n이 되면 perm이 완성된 순열이므로 출력 후 반환
  • 그렇지 않다면, used[i]가 false인 원소를 찾아 순열에 포함
• 사용 처리 및 탐색
  • used[i] = True, perm.append(arr[i]) 수행 후 depth = 1로 재귀 호출
• 되돌리기(backtrack)
  • 재귀 호출이 끝난 뒤 perm.pop(), used[i] = False로 복구

시간 복잡도와 최적화

• 기본 시간 복잡도
  • 백트래킹은 본질적으로 모든 경우의 수를 탐색(완전 탐색)할 수 있으므로, 경우의 수가 엄청나다면 최악 시 지수 시간(Exponential)이 될 수 있음
• 가지치기의 중요성
  • 미리 불가능한 부분을 배제하면, 지수적 탐색에서 상당한 절감을 이룰 수 있음
• 메모이제이션(Memoization) + 백트래킹
  • 일부 문제에서는 현재 상태가 반복해서 나타날 수 있으므로, 중복 상태를 저장하고 재탐색하지 않게 만들 수 있음 (ex. DP 기반 백트래킹)

구현 시 주의사항

• 정확한 가지치기 조건 설정
  • 문제마다 불가능함을 즉시 판별할 수 있는 조건을 정확히 세우고, 해당 조건에 해당하면 곧바로 종료
  • 가지치기가 제대로 설정되지 않으면 불필요한 경로를 모두 탐색
• 상태 복원
  • 재귀 함수가 종료된 뒤, 직전 상태로 되돌아갈 수 있도록 변경 사항을 복원(undo)해야 함
• 전역 변수 및 전역 자료구조 사용 시 동기화 주의
  • 방문 배열, 전역 리스트 등을 쓸 때, 재귀 호출 간에 부적절하게 공유되지 않도록 관리
• 시간 복잡도
  • 문제의 입력 범위를 확인하고, 백트래킹으로 해결 가능한 수준인지 검토
  • 필요 시 더 효율적인 알고리즘(ex. DP, 최적화된 탐색)을 고려
• 재귀 제한
  • 매우 큰 입력일 경우, 스택 깊이가 한계를 초과할 수 있음

대표 예시 문제

순열 / 조합 문제

• 순열 문제는 주어진 배열 및 집합의 모든 순열(permutation)을 생성하는 문제이며, 조합 문제는 주어진 배열 및 집합의 원소 중 특정 개수를 뽑는 모든 조합(combination)을 생성하는 문제
• 대표적인 순열 / 조합 문제 (대표적으로 백준의 N과 M 문제 시리즈(1 ~ 12)가 있다.)
  • 15649번: N과 M (1)
  • 15650번: N과 M (2)
  • 12980번: 좋아하는 수열

N-Queen 문제

• N x N 체스판에 N 개의 퀸(Queen)이 서로 공격하지 않도록 배치하는 모든 경우의 수(또는 한 가지 해)를 찾는 문제
• 9663번: N-Queen
• 30242번: 🧩 N-Queen (Easy)

백트래킹 핵심 요약

• 백트래킹은 모든 경우의 수를 탐색하는 과정에서 유망하지 않은 경우는 미리 포기함으로써 탐색 효율을 높이는 재귀 기반의 알고리즘 기법
• 재귀 기반의 기본 매커니즘(콜 스택, 상태 복원)에서 가지 치기를 추가하면 백트래킹 알고리즘이 됨
• 백트래킹 알고리즘은 코딩 테스트나 알고리즘 문제에서 조합 탐색이 필요한 거의 모든 상황에서 유용하게 사용됨