[Python] 알고리즘 개념4 - 재귀와 백트래킹

---

 

🚀 1. 재귀 함수란?

재귀는 함수가 자기 자신을 부르는 것을 말해요.

 

예를 들어, 거울을 거울에 비추면 끝없이 반복되는 모습을 본 적 있나요? 재귀 함수도 비슷해요. 함수가 자기 자신을 계속 부르지만, 언젠가는 멈춰야 해요. 이걸 "기본 종료 조건 (Base Case)" 이라고 해요.

def 인사(n):
    if n == 0:  # 종료 조건
        return
    print("안녕!")
    인사(n - 1)  # 자기 자신을 호출

인사(3)

💡 이해하기 쉽게 설명하자면: 친구에게 "안녕!"이라고 말하고, 그 친구도 또 다른 친구에게 "안녕!"이라고 말하는 방식이에요. 하지만 친구가 3명까지만 전달하고 더 이상 말하지 않도록 멈춰야 해요. 이걸 "기본 종료 조건(Base Case)" 이라고 부릅니다!

**재귀(Recursion)**란 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 기법입니다. 주로 분할 정복(Divide & Conquer) 방식에서 활용됩니다.

 

💡 재귀 함수의 핵심 요소

• 기본 종료 조건 (Base Case): 무한 루프 방지를 위해 반드시 필요합니다.
• 자기 자신 호출 (Recursive Case): 문제를 작게 나누어 해결합니다.

 

📌 재귀 함수의 기본 구조:

# 재귀 함수 예제 (팩토리얼 계산)
def factorial(n):
    if n == 0:
        return 1  # 종료 조건 (Base Case)
    return n * factorial(n - 1)  # 자기 자신 호출 (Recursive Case)

print(factorial(5))  # 출력: 120

➡ 재귀를 사용하면 문제를 더 직관적으로 표현할 수 있지만, 과도한 재귀 호출은 성능 저하를 초래할 수 있습니다.

---

 

 

🚀 2. 재귀 호출의 작동 원리

재귀 함수는 마치 우리가 **러시아 인형(마트료시카)**을 열어가는 것과 같아요. 큰 인형 안에 작은 인형이 있고, 다시 그 안에 더 작은 인형이 있는 식으로 계속 들어가요. 하지만 언젠가는 가장 작은 인형을 만나게 되죠. 이때부터 다시 인형을 하나씩 덮어가면서 원래 상태로 돌아오는 것처럼, 재귀 함수도 맨 마지막 호출부터 차례로 종료됩니다.

 

또 다른 예로, 쌓인 접시를 생각해볼까요?

• 새 접시를 위에 올릴 때마다 먼저 올린 접시를 기억해야 해요.
• 마지막 접시까지 쌓이면, 그때부터 하나씩 제거해야 하죠.
• 이것이 재귀 호출 스택의 원리와 같아요!

 

📌 재귀 호출 흐름 (팩토리얼 3 계산 과정)

재귀 함수가 호출될 때, 함수 호출 스택(Call Stack)에 각 단계의 상태가 저장됩니다. 함수가 종료될 때마다 스택에서 제거됩니다.

factorial(3) → 3 * factorial(2)
factorial(2) → 2 * factorial(1)
factorial(1) → 1 * factorial(0)
factorial(0) → 1 (Base Case)

➡ 결과적으로 3 * 2 * 1 * 1 = 6이 반환됩니다.

 

💡 스택 메모리 주의

• 재귀 호출이 너무 깊어지면 **스택 오버플로(Stack Overflow)**가 발생할 수 있습니다.
• Python에서는 기본적으로 최대 재귀 깊이가 1000으로 제한되어 있습니다.
• sys.setrecursionlimit()을 사용하여 변경할 수 있지만, 과도한 변경은 프로그램 충돌을 일으킬 수 있습니다.

---

 

 

🚀 3. 재귀 함수의 시간복잡도

재귀 함수의 실행 속도를 계산하는 것은 음식을 조리하는 과정과 비슷해요. 예를 들어, 피보나치 수열을 비효율적인 방식으로 구현하면 같은 재료(값)를 여러 번 사용하게 되어 요리를 여러 번 반복하는 셈이죠. 하지만 메모이제이션(Memoization)을 활용하면 한 번 만든 요리를 저장해두고 바로 사용할 수 있어요. 이렇게 하면 불필요한 재귀 호출을 줄여서 훨씬 빠르게 계산할 수 있습니다!

 

또 다른 예로, 학교에서 시험 문제를 푸는 방법을 떠올려보세요.

• 한 문제를 풀 때, 이미 계산했던 내용을 활용하면 시간을 절약할 수 있어요.
• 하지만 같은 문제를 반복해서 다시 풀면 시간이 오래 걸리죠.
• 메모이제이션을 사용하면 한 번 계산한 값은 저장하여 다시 계산하지 않도록 만들 수 있어요!

➡ 이런 최적화 기법을 사용하면, 피보나치 수열 계산 속도를 O(n) 수준으로 줄일 수 있어요!

재귀 함수의 시간복잡도를 분석할 때는 호출 횟수와 각 호출에서 수행하는 연산을 고려해야 합니다.

 

✅ 팩토리얼 재귀 호출의 시간복잡도

• factorial(n)은 n번 호출되므로 **O(n)**입니다.

 

✅ 피보나치 수열의 재귀 구현 (비효율적인 방식)

# 피보나치 수열 (비효율적인 재귀)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

💡 문제점: 중복 계산이 많아 **O(2^n)**의 시간복잡도를 가집니다. ➡ 해결 방법: **메모이제이션(Memoization) 또는 동적 프로그래밍(DP)**을 사용하여 중복 연산을 줄일 수 있습니다.

 

📌 메모이제이션 적용 예시:

# 피보나치 수열을 메모이제이션을 사용하여 최적화
dp = {}
def fibonacci(n):
    if n in dp:
        return dp[n]
    if n <= 1:
        return n
    dp[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return dp[n]

➡ 중복 연산을 방지하여 성능을 획기적으로 개선할 수 있습니다.

---

 

 

🚀 4. 백트래킹이란?

백트래킹은 미로에서 길을 찾는 것과 비슷해요. 만약 막다른 길을 만나면 그 자리에서 멈추는 게 아니라, 뒤로 돌아가 다른 길을 찾아야 하죠. 이 과정에서 가능성이 없는 길을 미리 차단하면(Pruning) 더 효율적으로 정답을 찾을 수 있어요.

 

예를 들어, 퍼즐을 푸는 과정을 생각해볼까요?

• 퍼즐 조각을 맞출 때, 먼저 하나를 시도해봐요.
• 만약 조각이 맞지 않으면 다시 되돌아가서 다른 조각을 시도해요.
• 이 과정이 반복되면서 결국 올바른 퍼즐이 완성됩니다.

 

💡 백트래킹을 활용하면, 모든 경우를 무작정 탐색하는 것이 아니라 불필요한 시도를 줄일 수 있어요!

**백트래킹(Backtracking)**은 가능한 모든 경우를 탐색하면서, **불가능한 경로는 조기에 차단(Pruning)**하는 기법입니다.

 

📌 백트래킹의 핵심 원리:

1. 현재 상태에서 가능한 모든 선택지를 시도한다.
2. 만약 유효하지 않은 선택지라면 즉시 되돌아간다 (Backtracking).
3. 올바른 해결 방법을 찾으면 종료한다.

 

💡 대표적인 백트래킹 문제

• N-Queen 문제: 체스판 위에 N개의 퀸을 서로 공격하지 않도록 배치하는 문제
• 부분집합 & 순열 생성: 모든 조합을 구하는 문제
• 미로 탐색: 경로를 찾는 문제

 

➡ 브루트포스(Brute Force)와의 차이점:

• 브루트포스: 모든 경우를 무식하게 다 탐색함.
• 백트래킹: 불필요한 탐색을 가지치기(Pruning)하여 효율적으로 탐색함.

---

 

 

🚀 5. 백트래킹 활용 예제

 

✅ N-Queen 문제 (백트래킹 적용)

def is_safe(board, row, col, n):
    for i in range(row):
        if board[i] == col or abs(board[i] - col) == row - i:
            return False
    return True

def solve_n_queens(board, row, n):
    if row == n:
        print(board)
        return
    for col in range(n):
        if is_safe(board, row, col, n):
            board[row] = col
            solve_n_queens(board, row + 1, n)
            board[row] = -1

n = 4
board = [-1] * n
solve_n_queens(board, 0, n)

 

💡 설명:

• is_safe() 함수는 현재 퀸이 다른 퀸과 충돌하지 않는지 검사합니다.
• solve_n_queens() 함수는 백트래킹을 이용해 가능한 모든 퀸 배치를 찾습니다.
• 비효율적인 탐색을 줄이기 위해 **유망하지 않은 경우를 빠르게 배제(Pruning)**합니다.

➡ 이렇게 하면 탐색 범위를 크게 줄일 수 있습니다.

---

 

 

✅ 마무리 정리

• 재귀 함수는 자기 자신을 호출하는 함수로, 종료 조건(Base Case)이 필요합니다.
• 재귀 함수는 스택 메모리를 사용하므로 깊은 재귀 호출 시 오버플로우에 주의해야 합니다.
• 백트래킹은 가능한 모든 경우를 탐색하면서 잘못된 경로를 조기에 차단하는 탐색 기법입니다.
• N-Queen 문제와 같은 조합 최적화 문제에서 백트래킹이 자주 사용됩니다.