재귀 함수 (Recursive Function)

2026. 06. 09

들어가는 말

재귀 함수는 특정 문법이 아니다.
함수 내부에서 함수 자기 자신을 다시 호출하는 방식이다.
주어진 문제에 대해 같은 논리를 반복해서 적용하면서, 호출할 때마다 인자 값을 변화시켜 문제를 더 작은 문제로 나누어 해결한다.
이렇게만 들으면 반복문과 비슷해 보인다.

차이는 함수 호출을 처리하는 방식에 있다.
함수 호출이 일어나면 스택 메모리 영역에 해당 함수의 Stack Frame이 만들어지고, 이렇게 호출마다 프레임이 쌓인 구조를 Call Stack(호출 스택)이라고 한다.
재귀 함수는 별도의 Stack 자료구조를 직접 만들지 않고, 함수 호출 과정에서 사용되는 Call Stack을 활용한다.

팩토리얼 예제

팩토리얼을 구하는 코드는 반복문(for, while)으로도 작성할 수 있다.
하지만 재귀 함수를 사용하면 다음처럼 표현할 수 있다.

#include <stdio.h>

int factorial(int n)
{
    if (n <= 1)
    {
        return 1;
    }

    return n * factorial(n - 1);
}

int main(void)
{
    int n = 5;

    printf("%d! = %d\n", n, factorial(n));
}

처음 재귀 함수를 보면 이상하게 느껴질 수 있다.
factorial 함수의 중괄호가 아직 끝나지도 않았는데, 그 안에서 다시 factorial을 호출하기 때문이다.
마치 함수 정의가 끝나기 전에 자기 자신을 사용하는 것처럼 보인다.

하지만 함수 호출은 그 함수로 실행 흐름을 옮겼다가, 함수 실행이 끝나면 다시 원래 위치로 돌아오는 동작이다.
컴파일이 끝나면 함수는 실행 코드가 놓인 메모리 위치를 갖는다.
함수 호출은 그 위치로 실행 흐름을 옮겨 명령어들을 실행하는 동작이다.
factorial(n - 1)을 만나면 프로그램은 다시 factorial 함수의 시작 위치로 이동해 코드를 실행한다.

재귀 함수의 필수 조건

재귀 함수가 올바르게 동작하려면 두 가지 조건이 반드시 필요하다.

종료 조건(Base Case, Ending Condition)
- 재귀 호출을 멈추는 조건이다.
  위 예제에서는 if (n <= 1) return 1;이 종료 조건이다.
- 종료 조건이 없으면 함수 호출이 끝나지 않는다.
  그러면 Stack Frame이 계속 쌓이고, Stack Memory의 한계를 넘어 스택 오버플로우(Stack Overflow)가 발생한다.
반복 구간(Recursive Case)
- 인자를 바꿔 자기 자신을 다시 호출하는 구간이다.
  위 예제에서는 return n * factorial(n - 1); 전체가 반복 구간이고, 그중 실제로 자기 자신을 다시 호출하는 부분은 factorial(n - 1)이다.
- 함수를 호출할 때마다 문제의 크기를 변화시켜 종료 조건에 도달하도록 해야 한다.

사용 이유

반복문과 유사한 면도 있고 복잡해 보이는 재귀 함수를 왜 사용해야 할까?

특정 유형의 문제에 적합하다

트리 탐색, 하노이의 탑처럼 문제 자체가 더 작은 문제로 나누어지고, 그 작은 문제도 똑같은 방식으로 풀리는 구조라면 재귀가 자연스러운 문제 해결 방법이다.

반복문으로 표현하기 복잡한 경우

깊이를 알 수 없는 중첩 구조(폴더 탐색, JSON 파싱 등)는 반복문으로 구현하면 코드가 매우 복잡해진다.
각 단계의 상태(현재 위치, 처리한 항목, 복귀할 위치)를 직접 관리하기 위해 Stack 자료구조를 만들어 관리해야 하기 때문이다.
하지만, 재귀 함수를 이용하면 이미 존재하는 Call Stack을 활용하기 때문에 Stack을 관리할 필요가 없어 문제의 핵심 탐색 논리에 집중할 수 있다.

수학 정의를 쉽게 코드로 옮길 수 있다

#include <stdio.h>

/*
    Fibonacci Sequence Definition

    F(0) = 0
    F(1) = 1
    F(n) = F(n - 1) + F(n - 2)  (n >= 2)

    Sequence: 0 1 1 2 3 5 8 13 21 ...
*/
int fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main(void)
{
    int n = 5;

    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));
}

피보나치 수의 수학 정의는 재귀 구조 그 자체이기 때문에,
재귀 함수를 사용하면 수학 정의를 코드로 자연스럽게 옮길 수 있다.

단점

스택 오버플로우 (Stack Overflow)
- 함수 종료 없이 계속 호출되거나 재귀 호출의 깊이가 너무 깊으면 Call Stack에 누적된 Stack Frame이 한계에 도달해 Stack Overflow가 발생한다.
성능 오버헤드 (Performance Overhead)
- 함수 호출마다 새로운 Stack Frame을 생성하고 함수 종료 시 복귀 주소로 점프하고 매개변수 정리 같은 작업들이 일어난다.
중복 계산
- 피보나치 수를 보면 동일한 인자에 대한 계산이 여러 번 반복되어 불필요한 함수 호출이 반복된다.
복잡한 디버깅
- Stack Frame이 계속 쌓여 실행 흐름을 추적하기 어렵다.

단점 보완 기법

Memoization: 한 번 계산한 결과를 메모리에 저장해 두어 중복 계산을 방지한다.
Cycle Detection: 이미 방문한 노드를 추적하여 Stack Overflow에 빠지는 것을 막는다.

재귀 함수 vs 반복문

대부분의 문제는 상호 변환이 가능하다.
문제의 구조, 코드 가독성, 성능을 고려해 해결 방법을 택해야 한다.

복잡한 계층 구조나 분할 정복처럼 문제가 같은 형태의 작은 문제로 나누어지는 경우에는 재귀 함수가 자연스럽다.
1 ~ n까지의 합이나 곱처럼 단순히 값을 누적하는 문제는 반복문이 더 단순하다.
재귀 함수가 자연스러운 문제라도 호출 깊이가 입력에 따라 지나치게 깊어질 수 있다면, 반복문과 명시적인 Stack 자료구조를 사용하는 방법을 고려해보자.