재귀함수 작성 가이드

알고리즘 문제 풀이(특히 백준, 프로그래머스 등)에서 DFS, 백트래킹, 분할 정복 등을 풀기 위해 반드시 정복해야 하는 산이 바로 재귀함수(Recursion)입니다.

처음에는 머릿속에서 모든 과정을 다 따라가려고 해서 헷갈리기 쉬운데요. 코딩 테스트에서 재귀함수를 설계할 때 반드시 지켜야 하는 5단계 핵심 요령을 정리해 드립니다.

1. 함수의 '목적' 명확히 정의하기

재귀함수를 짤 때 가장 먼저 해야 할 일은 이 함수가 정확히 무엇을 하는 함수인지 한 문장으로 정의하는 것입니다.

나쁜 예: def dfs(n): (그냥 n을 넣고 돈다)
좋은 예: def get_sum(n): (1부터 n까지의 합을 구해서 반환하는 함수다)

2. 종료 조건(Base Case) 가장 먼저 쓰기 ⭐️

재귀함수는 무한 루프에 빠지기 매우 쉽습니다(파이썬은 RecursionError 발생). 따라서 함수가 시작되자마자 "어떤 상황에서 재귀를 멈추고 돌아갈 것인가?"를 최상단에 적어야 합니다.

pythondef factorial(n):
    # 1. 종료 조건 (Base Case)
    if n <= 1: 
        return 1

3. 문제를 가장 작은 단위로 쪼개기 (점화식)

내가 구해야 하는 값(n)을 나보다 한 단계 작은 값(n-1)을 이용해 어떻게 구할지 식을 세웁니다. 이것을 수학에서는 점화식이라고 합니다.

$n!$ 은 $n \times (n-1)!$ 과 같습니다.
피보나치 수열 $F(n)$ 은 $F(n-1) + F(n-2)$ 과 같습니다.

pythondef factorial(n):
    if n <= 1:
        return 1
        
    # 2. 점화식 (재귀 호출)
    return n * factorial(n - 1)

4. 필요한 '상태'는 매개변수(Parameter)로 넘기기

백트래킹이나 DFS 문제를 풀 때 가장 중요한 부분입니다. 현재 어디까지 탐색했는지, 지금까지의 합이 몇인지 같은 진행 상황(상태) 을 매개변수에 담아서 다음 함수로 넘겨주어야 합니다.

python# 배열 안에서 더해서 특정 값이 되는 경우를 찾는 DFS 예시
def dfs(index, current_sum):
    # 종료 조건: 끝까지 다 탐색했을 때
    if index == len(arr):
        if current_sum == target:
            print("찾았다!")
        return

    # 1) 현재 숫자를 선택하는 경우
    dfs(index + 1, current_sum + arr[index])
    
    # 2) 현재 숫자를 선택하지 않는 경우
    dfs(index + 1, current_sum)

5. '재귀적 믿음' 가지기 (추상화)

이게 심리적으로 가장 중요한 요령입니다. 사람이 머릿속으로 f(5)가 f(4)를 부르고 f(4)가 f(3)을 부르는 과정을 끝까지 추적하려고 하면 무조건 꼬입니다. "내가 짠 factorial(n-1)이 어쨌든 알아서 완벽하게 $(n-1)!$ 값을 구해올 것이다" 라고 굳게 믿고, 현재 단계(n)에서 해야 할 일만 코드로 적으셔야 합니다.

요약 템플릿

pythondef recursive_function(현재_상태):
    # 1. 종료 조건 (가장 중요)
    if 정답을_찾았거나_끝에_도달했는가?:
        return 정답_또는_처리
        
    # 2. 다음 상태로 넘어가기 위한 작업 (점화식 / 재귀 호출)
    for 다음_상태 in 가능한_모든_경우의수:
        recursive_function(다음_상태)