재귀

재귀란?

재귀(recursion) 는 함수가 자기 자신을 부르는 기법입니다. 큰 문제를 같은
모양의 더 작은 문제로 쪼개어, 충분히 작아지면 직접 답하는 방식으로 풉니다.

재귀 함수에는 반드시 두 가지가 있어야 합니다.

• 기저 조건(base case): 더 쪼개지 않고 즉시 답하는 가장 작은 경우.
• 재귀 호출(recursive case): 더 작은 문제로 자신을 부르는 부분.

기저 조건이 없거나 잘못되면 무한히 자신을 불러 스택 오버플로가 납니다.

1. 가장 단순한 예: 팩토리얼

\(N! = N \times (N-1)!\)이고 \(0! = 1\)입니다. 이 정의가 그대로 코드가 됩니다.

long long fact(int n) {
    if (n <= 1) return 1;        // 기저 조건
    return n * fact(n - 1);      // 더 작은 문제
}

fact(4)는 4 * fact(3)을, 그것은 3 * fact(2)를... 부르며 내려가다가
fact(1)에서 멈추고, 그 값을 곱하며 거슬러 올라옵니다.

2. 호출 스택으로 이해하기

재귀는 호출 스택 위에서 동작합니다. fact(4)의 호출이 쌓였다가 풀리는 모습:

fact(4) 호출 → fact(3) 호출 → fact(2) 호출 → fact(1) = 1 반환
fact(2) = 2*1 = 2 반환 → fact(3) = 3*2 = 6 → fact(4) = 4*6 = 24

이 "내려갔다가 올라오는" 흐름을 머릿속에 그릴 수 있으면 재귀를 이해한 것입니다.

3. 재귀로 자연스러운 문제들

어떤 문제는 본질적으로 재귀적입니다.

특히 트리와 그래프 탐색(DFS), 분할 정복, 백트래킹, DP가 모두
재귀 위에 세워집니다. 재귀는 Silver 이후 거의 모든 주제의 토대입니다.

4. 재귀와 반복의 관계

모든 재귀는 반복문(+스택)으로 바꿀 수 있고, 반대도 가능합니다. 단순 반복은
반복문이 빠르고 안전하지만, 분기가 여러 갈래인 탐색은 재귀로 짜는 것이
압도적으로 간결합니다. 상황에 맞게 고릅니다.

5. 위험: 깊이와 중복 계산

• 깊이 제한: 재귀가 너무 깊으면 스택이 넘칩니다. C++ 기본 스택은 보통 수십만
  깊이, 파이썬은 기본 1000 깊이로 더 얕습니다.
• 중복 계산: 단순 재귀 피보나치는 같은 값을 지수 번 다시 계산해
  \(O(2^N)\)입니다. 메모이제이션(DP)으로 해결합니다 — 다음 주제로 이어집니다.

정리

재귀 = 기저 조건 + 자기 호출. "큰 문제를 같은 모양의 작은 문제로 쪼갤 수 있는가?"
를 물어보세요. 답이 예이면 재귀가 가장 자연스러운 도구입니다.

재귀를 안전하게 짜기

재귀의 원리를 코드로 옮기고, 깊이 제한·중복 계산 같은 실전 함정을 다룹니다.

1. 표준 골격

모든 재귀 함수는 같은 형태를 따릅니다.

ReturnType solve(상태) {
    if (기저 조건) return 직접 답;     // 1) 멈추는 곳
    // 2) 더 작은 상태로 자신을 호출하고
    // 3) 그 결과를 모아 현재 답을 만든다
    return 조합(solve(더 작은 상태), ...);
}

이 골격에 문제를 끼워 맞추는 것이 재귀 풀이의 전부입니다.

2. 피보나치: 느린 버전과 빠른 버전

// 느림: O(2^N) — 같은 값을 수없이 다시 계산
long long fib_slow(int n) {
    if (n <= 1) return n;
    return fib_slow(n - 1) + fib_slow(n - 2);
}

// 빠름: 메모이제이션 O(N)
long long memo[100];
long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];          // 이미 계산했으면 재사용
    return memo[n] = fib(n - 1) + fib(n - 2);
}

import sys
from functools import lru_cache

sys.setrecursionlimit(300000)             # 깊은 재귀 대비

@lru_cache(maxsize=None)                  # 자동 메모이제이션
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

memo 배열(또는 @lru_cache)을 한 번 본 값을 저장해 두는 것만으로 지수 시간이
선형 시간이 됩니다. 이것이 바로 DP의 출발점입니다.

3. 분할 정복 예: 거듭제곱 빠르게

\(a^n\)을 \(O(\log n)\)에 계산합니다. 지수를 반으로 쪼개는 재귀입니다.

long long power(long long a, long long n, long long mod) {
    if (n == 0) return 1;
    long long half = power(a, n / 2, mod);
    long long res = half * half % mod;
    if (n & 1) res = res * a % mod;        // 홀수면 a 한 번 더
    return res;
}

한 번 호출할 때마다 지수가 절반이 되므로 깊이가 \(\log n\)입니다.

4. 파이썬의 재귀 깊이

파이썬은 기본 재귀 깊이가 1000으로 얕습니다. 깊은 재귀(예: \(10^5\) 깊이의
DFS)에서는 반드시 늘려야 합니다.

import sys
sys.setrecursionlimit(10**6)

너무 깊으면(수백만) 파이썬에서는 아예 반복문 + 명시적 스택으로 바꾸는 편이
안전합니다.

5. 흔한 실수

• 기저 조건 누락/오류 — 무한 재귀 → 스택 오버플로. 가장 먼저 점검할 곳.
• 기저 조건이 도달 불가 — 예: n을 줄이지 않고 호출하거나, 짝수만 줄이는데
  홀수가 들어오는 경우.
• 메모이제이션 빠뜨림 — 분기가 겹치는 재귀는 메모 없으면 지수 폭발.
• 파이썬 깊이 제한 — DFS 전에 setrecursionlimit 잊지 말기.
• 메모 배열 초기값 충돌 — 0이 유효한 답일 수 있으면 "계산 여부"를 따로
  표시(예: -1로 초기화)하세요.

6. 패턴 알아보기

• "같은 모양의 작은 문제로 쪼갤 수 있다" → 재귀.
• "분기가 겹친다" → 재귀 + 메모이제이션(DP).
• "절반으로 나눠 합친다" → 분할 정복.
• 깊이가 문제 되면 반복문 + 스택으로 전환.

실전에서 재귀 문제 알아보기

재귀는 도구라기보다 문제를 읽는 방식입니다. "이 문제의 큰 버전이 작은
버전 몇 개로 쪼개지는가?"를 묻는 순간 재귀 풀이가 보이기 시작합니다.

1. 출제 신호

• 문제 구조 자체가 자기 닮음 — 프랙탈 별 찍기, 쿼드트리 압축, 칸토어 집합.
  그림이 "같은 모양의 축소판"으로 이루어져 있으면 재귀입니다.
• "절반으로 나누어" — 종이 자르기, 구간을 반씩 처리. 분할 정복의 입구입니다.
• 하노이 탑처럼 "큰 것을 옮기려면 작은 것을 먼저" — 답의 정의가 더 작은
  입력의 답으로 서술됩니다.
• 수열의 점화식이 주어짐 — \(f(n) = f(n-1) + f(n-2)\)류. 정의를 그대로
  코드로 옮길 수 있습니다.
• 트리·중첩 구조의 순회(이후 DFS로 일반화).

2. 풀이 결정 절차

1. 상태(인자)를 정의합니다 — "지금 처리 중인 부분"을 숫자 몇 개로 표현?
   (예: 격자 왼쪽 위 좌표 + 한 변 길이)
2. 기저 조건을 정합니다 — 더 못 쪼개는 가장 작은 입력에서 무엇을 하나?
3. 호출 트리의 크기를 셉니다 — 한 호출이 자식을 몇 개 만들고 깊이는
   얼마인가? 같은 입력이 반복 계산되면 메모이제이션이 필요하다는 뜻입니다.
4. 재귀 깊이가 수만을 넘으면 반복문/스택 변환이나 한도 조정을 계획합니다.

3. 자주 하는 실수

• 같은 부분 문제를 다시 계산. \(f(n)=f(n-1)+f(n-2)\)를 그대로 짜면
  \(O(2^n)\)입니다. 호출 트리에 같은 인자가 반복되면 결과를 저장하세요.

import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)        # 파이썬 기본 한도는 약 1000

@lru_cache(maxsize=None)
def f(n):
    if n <= 1:                      # 기저 조건을 가장 먼저
        return n
    return f(n - 1) + f(n - 2)

• 기저 조건이 닿지 않음. \(n\)을 2씩 줄이는데 기저가 n == 0뿐이면 홀수
  입력에서 무한 재귀입니다. 모든 경로가 기저에 도달하는지 확인하세요.
• 파이썬 재귀 한도. 기본 약 1000이라 깊은 재귀는
  sys.setrecursionlimit을 올려야 합니다. C++도 지역 배열이 크면 스택이
  터질 수 있습니다.
• 인자로 큰 컨테이너를 복사해 전달. 리스트/벡터를 값으로 넘기면 호출마다
  \(O(N)\) 복사가 발생합니다. 참조나 인덱스 범위로 넘기세요.
• 출력 순서 혼동. "호출 전 출력"(전위)과 "호출 후 출력"(후위)은 결과가
  완전히 다릅니다. 하노이처럼 순서가 답인 문제는 위치를 신중히.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 것 → 어려운 것 순서입니다. 점화식
직역 문제로 손을 푼 뒤 프랙탈 출력, 하노이류로 올라가는 흐름을 권합니다.

문제마다 코드를 짜기 전에 호출 트리를 3단계만 손으로 그려 보세요. 상태
정의가 맞는지 즉시 드러납니다. 3문제 이상 풀어 클리어하면 레이팅의
CLASS 보너스에 반영됩니다.