재귀 설계와 메모이제이션, 분할 정복 거듭제곱

재귀 함수를 처음 배울 때 헷갈렸던 건 “언제 멈추게 할까”가 아니라 “이게 얼마나 느린가”였다. 이 글에서는 재귀를 기저 조건 + 문제 축소라는 두 부품으로 조립하는 법과, 그렇게 만든 함수의 시간복잡도를 호출 트리 모양으로 읽는 법을 이야기하려 한다. 구현으로는 피보나치의 지수 폭발을 메모이제이션으로 잡는 과정, DFS를 재귀와 반복 스택 두 방식으로 짜서 비교한 것, 그리고 거듭제곱을 분할 정복으로 O(logN)까지 줄인 것을 다룬다.

재귀 설계의 두 부품 — 기저 조건과 문제 축소

재귀 설계의 뼈대는 두 가지다. 문제 크기를 줄이는 설계가 핵심이고, 시간복잡도는 호출 트리 구조로 판단한다. 순서상으로는 반드시 기저 조건부터 설계한다.

구성	목적	실수 시 문제
기저 조건(Base Case)	종료 보장	무한 재귀
재귀 단계(Recursive Step)	문제 축소	호출 깊이 과다

if (n == 0) return 1;
return n * f(n - 1);

재귀 호출과 스택 메모리

호출마다 스택 프레임(함수 호출 정보를 담는 메모리 단위)이 하나씩 쌓인다. 그래서 공간복잡도는 O(호출 깊이) — 깊이가 N이면 공간도 O(N)이다. 깊이가 10^5를 넘어갈 수 있으면 위험하니 반복문 전환을 고려한다.

단순 재귀 vs 메모이제이션

방식	시간복잡도	특징
피보나치 단순 재귀	O(2^N)	중복 호출
메모이제이션	O(N)	결과 저장

fibo(n-1) + fibo(n-2)는 같은 값을 여러 번 다시 계산해서 호출 수가 지수로 늘어난다. 계산 결과를 배열에 저장해 두면(메모이제이션) O(N)으로 떨어진다.

if (memo[n] != -1) return memo[n];
memo[n] = f(n - 1) + f(n - 2);

DP(동적 계획법)로 전환할 수 있는 형태이며, memo 배열 초기화를 빼먹지 않는 게 포인트다.

DFS: 재귀 vs 반복(Stack)

구현	시간	공간
재귀 DFS	O(V+E)	O(depth)
stack DFS	O(V+E)	O(V)

재귀는 콜 스택을 암묵적 스택으로 쓰는 것이고, 반복 구현은 명시적 stack을 쓴다.

void DFS(int node) {
    visited[node] = true;
    for (auto next : graph[node])
        if (!visited[next]) DFS(next);
}

visited 처리 순서가 중요하고, 그래프 깊이가 크면 반복 구현을 권장한다.

지수 연산 최적화 (분할 정복)

방식	시간복잡도
단순 재귀 pow	O(N)
분할 정복 pow	O(logN)

N이 짝수면 pow(X, N) = pow(X, N/2)²로 문제 크기를 절반씩 줄이는 게 핵심 아이디어다.

double half = pow(x, n / 2);
return (n % 2 == 0) ? half * half : half * half * x;

N==0 기저 조건을 반드시 두고, long long 오버플로우를 주의한다.

재귀가 맞는 문제, 아닌 문제

분할 정복(병합정렬, 퀵정렬)이나 트리/그래프 탐색처럼 구조가 자연스럽게 분기되는 문제는 재귀가 효율적이다. 반대로 단순 반복 누적 문제나 깊이가 큰 선형 구조는 재귀로 짤 이유가 없다.

시간복잡도 판단 기준은 호출 패턴으로 잡는다. 호출이 1개씩 감소하면 O(N), 2개씩 분기하면 O(2^N), 크기가 절반씩 줄면 O(logN). 실제 예로 fibo 단순 재귀는 O(2^N), pow 분할 정복은 O(logN), DFS는 O(V+E)다.

실전 체크리스트

• 깊이 최대치 계산 먼저
• 중복 호출 여부 확인
• 메모이제이션 가능 여부 판단
• 스택 초과 가능성 점검
• 가능하면 반복문 전환 고려

같은 회차에 이어 들은 STL 컨테이너 복습(vector·set·map·반복자)과 컨테이너별 시간복잡도 비교는 이 글의 주제에서 벗어나 덜어냈다. 해당 내용은 STL 컨테이너 정리와 vector vs list에 더 깊게 정리해 두었다.

핵심 요약 — 재귀는 기저 조건 + 문제 축소가 뼈대이고, 시간복잡도는 호출 트리로 판단한다(1개씩 감소 O(N), 2개 분기 O(2^N), 절반 감소 O(logN)). 피보나치처럼 중복 호출이 있으면 메모이제이션으로 O(2^N)을 O(N)으로 줄인다.