재귀 알고리즘

CS·데이터사이언스 고등 · v1 · 🤖 LLM 버전

정의

재귀 알고리즘(recursive algorithm)이란 어떤 문제를 해결하기 위해 자기 자신을 더 작은 크기의 같은 문제로 호출하여 풀어 나가는 알고리즘을 말한다. 재귀 알고리즘은 반드시 두 부분으로 구성된다.

• 기저 조건(base case): 더 이상 자신을 호출하지 않고 답을 바로 내놓는 가장 작은 경우
• 재귀 단계(recursive step): 문제를 더 작은 부분 문제로 나누어 자기 자신을 다시 호출하는 과정

함수 $f$가 자기 자신을 호출하는 구조를 점화식 형태로 쓰면, 예를 들어 $n$의 계승(팩토리얼) $n!$은 다음과 같이 정의된다.

$$ f(n) = \begin{cases} 1 & (n = 0) \\ n \times f(n-1) & (n \geq 1) \end{cases} $$

이때 $f(n-1)$($f$에 $n-1$을 대입한 값)을 구하는 과정이 곧 $f(n)$을 구하는 과정 안에 들어 있으므로, 이를 재귀적으로 정의되었다고 한다.

직관

재귀는 "러시아 마트료시카 인형"을 여는 과정과 비슷하다. 가장 큰 인형을 열면 그 안에 조금 작은 인형이 있고, 그 인형을 또 열면 더 작은 인형이 나온다. 이 과정을 계속하다 보면 결국 더는 열리지 않는 가장 작은 인형(기저 조건)에 도달하고, 거기서부터 거꾸로 답을 조립하며 되돌아 나온다.

수학적으로는 수열의 점화식과 본질적으로 같은 아이디어다. $a_n$을 구하려면 $a_{n-1}$을 알아야 하고, $a_{n-1}$을 구하려면 $a_{n-2}$를 알아야 하는 식으로 거슬러 올라가다가, 초항(기저 조건)에서 멈추는 것이다. 재귀 알고리즘은 이 점화식의 아이디어를 프로그램(또는 알고리즘 절차)으로 그대로 옮긴 것이라고 볼 수 있다.

예시

예시 1. 계승 계산

$5! $을 재귀적으로 계산하면 다음과 같이 호출이 쌓였다가(스택), 기저 조건에서 되돌아온다.

$$ f(5) = 5 \times f(4) = 5 \times 4 \times f(3) = \cdots = 5\times4\times3\times2\times1\times f(0) = 120 $$

예시 2. 피보나치 수열

$F(n) = F(n-1) + F(n-2)$, $F(0)=0,\ F(1)=1$로 정의되는 수열도 재귀 알고리즘으로 표현된다. $F(4)$를 구하려면 $F(3)$과 $F(2)$를 먼저 구해야 하고, 이 둘은 다시 각각 $F(2), F(1)$과 $F(1), F(0)$을 필요로 한다. 같은 값 $F(2)$가 중복 계산되는 것을 볼 수 있는데, 이는 재귀 알고리즘의 시간복잡도가 커지는 대표적인 원인이다.

예시 3. 이진 탐색과의 관계

이진 탐색도 "범위의 가운데 값을 확인하고, 남은 절반에서 다시 같은 방법으로 찾는다"는 구조이므로 재귀 알고리즘으로 자연스럽게 표현된다. 매 호출마다 탐색 범위가 절반으로 줄어들므로 호출 횟수는 $\log_2 n$($2$를 밑으로 하는 로그) 번 정도다.

🌍 실생활 예시

컴퓨터의 폴더(디렉터리) 구조를 탐색할 때 재귀가 실제로 쓰인다. 한 폴더 안의 전체 파일 개수를 세는 프로그램은, "이 폴더 안의 파일 개수 = 이 폴더에 바로 있는 파일 수 + 하위 폴더 각각에 대해 같은 방법으로 센 개수의 합"으로 동작한다. 하위 폴더가 또 하위 폴더를 가질 수 있으므로, 더 이상 하위 폴더가 없는 폴더(기저 조건)를 만날 때까지 같은 절차를 반복 호출한다.

⚠️ 흔한 실수

• 잘못된 생각: 재귀 단계만 정확히 짜면 된다고 생각한다. → 왜 틀렸는지: 기저 조건이 없거나 잘못되면 호출이 끝없이 이어져 무한 재귀에 빠지고, 실제 프로그램에서는 스택 오버플로(stack overflow)로 이어진다. 기저 조건은 재귀의 필수 구성 요소다.
• 잘못된 생각: 재귀로 쓴 피보나치 계산이 반복문(iteration)으로 쓴 것보다 항상 효율적이거나 최소한 비슷할 것이라 생각한다. → 왜 틀렸는지: 예시 2에서 보듯 같은 부분 문제가 여러 번 중복 호출되면 시간복잡도가 지수적으로 커질 수 있다. 단순 재귀와 효율적인 알고리즘은 별개의 문제다.
• 잘못된 생각: 재귀 단계에서 문제가 "더 작아지는지" 확인하지 않고, 재귀 호출에 원래와 같거나 더 큰 크기의 값을 넘겨준다. → 왜 틀렸는지: 재귀가 반드시 종료하려면 매 호출마다 문제의 크기(위 예시의 $n$)가 기저 조건 쪽으로 줄어들어야 한다. 크기가 줄지 않으면 역시 무한 재귀가 된다.

확인 문제

1. $n! $을 반복문(for문)으로 계산하는 것과 재귀로 계산하는 것은 최종 결괏값이 같다. 그런데도 재귀적 정의를 따로 배우는 이유는 무엇일지, 계승의 점화식 $f(n) = n \times f(n-1)$이 문제를 "어떻게" 더 작게 만드는지에 주목하여 설명해 보아라.
2. 다음 재귀 정의에서 기저 조건과 재귀 단계를 각각 찾고, $g(4)$의 값을 구하여라. $$g(n) = \begin{cases} 2 & (n=1) \\ g(n-1) + 3 & (n \geq 2)\end{cases}$$
3. 피보나치 수 $F(5)$를 재귀 호출 트리로 그려 보면 $F(2)$가 몇 번 중복 계산되는지 세어 보아라. 이 중복이 $n$이 커질수록 왜 문제가 되는지 한 문장으로 설명하여라.

관련 개념

• 함수 — 재귀 알고리즘은 함수가 자기 자신을 호출하는 특수한 형태다.
• 수열 — 점화식으로 정의된 수열은 재귀 알고리즘의 수학적 원형이다.
• 시간복잡도 — 재귀 알고리즘의 효율성을 분석할 때 필요하다.
• 이진 탐색 — 재귀로 자연스럽게 표현되는 대표적인 알고리즘이다.