재귀(Recursion)란 무엇인가?
재귀는 큰 문제를 작은 단위로 나누어 해결하는 데 매우 유용한 프로그래밍 기법입니다. 각 재귀 호출은 그 자체로 또 다른 재귀 호출을 발생시키며, 이러한 과정이 반복되면서 문제가 점진적으로 해결됩니다.
재귀 함수의 핵심에는 두 가지 유형의 경우가 있습니다.
- 기저 사례(Base Case): 재귀가 언제 종료되어야 하는지를 알려주는 조건으로, 무한 루프를 방지하는 역할을 합니다.
- 재귀 사례(Recursive Case): 자신이 속한 함수를 다시 호출하며 문제를 단계적으로 축소해 나가는 부분입니다.
재귀적 해법이 자연스럽게 적용되는 대표적인 문제로는 팩토리얼(factorial) 계산이 있습니다. 팩토리얼 재귀 알고리즘은 n = 0일 때의 기저 사례와 n > 0일 때의 재귀 사례, 이 두 가지 경우로 구성됩니다.
백트래킹(Backtracking)이란 무엇인가?
백트래킹은 어떤 계산 문제에 대한 해답을 찾기 위한 범용 알고리즘입니다. 해답에 이르는 선택지를 한 단계씩 점진적으로 구축해 나가다가, 현재 경로가 유효한 해답으로 이어질 수 없다고 판단되면 해당 경로의 추가 처리를 즉시 중단하고 되돌아갑니다.
즉, 백트래킹을 사용하면 이전 선택이 잘못된 것으로 판명될 경우 그 선택을 취소(Undo)하고 다른 가능성을 탐색할 수 있습니다. 백트래킹은 본질적으로 재귀와 깊은 관련이 있으며, N-퀸(N-Queens) 문제, 미로 찾기, 스도쿠 풀이 등 조합 탐색 문제에서 널리 활용됩니다.
팩토리얼 재귀 예제
팩토리얼의 전형적인 재귀 구현은 다음과 같습니다.
def factorial(n):
# 기저 사례(base case) 검사
if n == 0:
return 1
# 계산을 수행한 뒤 재귀 호출
f = n * factorial(n - 1)
print(f)
return f
factorial(4)이 코드를 실행하면 1, 2, 6, 24가 순서대로 출력됩니다. factorial(4)를 계산하려면 초기 부모 호출에 더해 네 번의 재귀 호출이 필요합니다.
실행 흐름을 단계별로 살펴보면 다음과 같습니다.
- factorial(0) → 기저 사례에 도달하여 1을 반환
- factorial(1) → 1 × 1 = 1 출력
- factorial(2) → 2 × 1 = 2 출력
- factorial(3) → 3 × 2 = 6 출력
- factorial(4) → 4 × 6 = 24 출력
이처럼 재귀 함수는 가장 안쪽 호출부터 결과가 반환되면서 바깥쪽 호출로 거슬러 올라가며 최종 결과를 완성합니다. 기저 사례를 명확히 설정하는 것이 재귀 프로그래밍의 가장 중요한 원칙임을 기억하세요.