부른 순서대로 쌓이고 반대로 풀린다

2026년 9월 8일–C#기초

메서드 안에서 다른 메서드를 부를 수 있습니다. 그럼 자기 자신을 불러도 될까요. 됩니다.

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

    return n * Factorial(n - 1);
}

5! 는 5 × 4! 이고, 4! 는 4 × 3! 입니다. 큰 문제를 한 단계 작은 같은 문제로 바꾸는 것, 이게 재귀입니다.

재귀에는 두 부분이 있습니다. 한 단계 줄이는 식과, 더 줄일 수 없는 지점입니다.

종료 조건이 없으면 죽는다

더 줄일 수 없는 지점을 종료 조건이라고 합니다. 위 코드에서는 n <= 1 입니다.

이게 없으면 어떻게 될까요.

int Factorial(int n)
{
    return n * Factorial(n - 1);    // 종료 조건이 없습니다
}

5 는 4 를 부르고, 4 는 3 을, 3 은 2 를, 1 은 0 을, 0 은 -1 을 부릅니다. 끝나지 않습니다.

앞에서 본 무한 루프와 같은 실수인데 결과가 다릅니다. 무한 루프는 프로그램이 계속 돌기만 하고, 이건 StackOverflowException 으로 죽습니다.

왜 죽는지 보려면 호출이 어떻게 쌓이는지를 봐야 합니다.

호출은 쌓였다가 반대로 풀린다

앞에서 메서드를 부르면 돌아올 자리를 어딘가에 쌓아 둔다고 했습니다. 그 어딘가가 스택입니다. 나중에 넣은 것이 먼저 나오는 그 스택 맞습니다.

내려갈 때는 계산이 안 끝난 자리가 쌓입니다. Factorial(3) 은 3 × ? 까지 적어 두고 멈춰 있습니다. ? 를 알아야 끝납니다.

올라올 때 그 ? 가 하나씩 채워집니다. 가장 나중에 쌓인 것부터 풀립니다.

종료 조건이 없으면 내려가기만 하고 올라오지 않습니다. 쌓이는 자리는 무한하지 않습니다. 한계에 닿으면 StackOverflowException 입니다. 보통 수천에서 수만 번 깊이에서 터집니다.

반복문으로도 되는데 왜

Factorial 은 반복문으로도 씁니다.

int Factorial(int n)
{
    int result = 1;

    for (int i = 2; i <= n; i++)
    {
        result *= i;
    }

    return result;
}

이쪽이 더 낫습니다. 쌓이는 것이 없고, 깊이 걱정도 없습니다.

단순히 줄어드는 문제는 반복문이 낫습니다. 재귀가 어울리는 것은 갈래가 여럿으로 뻗는 구조입니다. 폴더 안에 폴더가 있고 그 안에 또 폴더가 있는 것, 트리 모양의 데이터 같은 것들입니다. 그런 걸 반복문으로 쓰려면 결국 스택을 직접 만들어서 쌓아야 합니다. 그럴 거면 이미 있는 호출 스택을 쓰는 편이 짧고 읽힙니다.

짧은 코드가 빠른 코드는 아니다

재귀의 진짜 함정은 깊이가 아니라 중복 계산입니다. 피보나치가 유명한 예입니다.

int Fib(int n)
{
    if (n <= 1) return n;

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

세 줄입니다. 문제 정의를 그대로 옮겨 적은 것처럼 깔끔합니다. 그런데 Fib(5) 를 부르면 무슨 일이 일어나는지 보면 이렇습니다.

Fib(5) 는 Fib(4) 와 Fib(3) 을 부릅니다. Fib(4) 는 다시 Fib(3) 과 Fib(2) 를 부릅니다. Fib(3) 을 두 번 계산합니다. 그리고 그 안에서 Fib(2) 를 또 여러 번 계산합니다.

n 을 40 으로 올려 보세요. 재귀 쪽은 수억 번입니다. 반복문으로 쓰면 40 번입니다.

코드가 짧다고 빠른 것은 아닙니다. 이 경우는 짧아서 오히려 감춰집니다. 세 줄짜리 코드가 수억 번을 도는 것이 눈에 안 보입니다.

이미 계산한 값을 어딘가에 저장해 두고 다시 쓰면 이 문제는 사라집니다. Dictionary 가 그런 저장에 어울립니다. 이렇게 계산 결과를 기억해 두는 방식을 메모이제이션이라고 부릅니다.

재귀를 쓸 때 확인할 것

반복문에서 “무엇이 이 조건을 거짓으로 만드는가” 를 확인했습니다. 재귀에서는 세 가지입니다.

종료 조건이 있는가. 없으면 죽습니다.
매번 그 조건에 가까워지는가. Factorial(n - 1) 처럼 줄어들어야 합니다. Factorial(n) 을 다시 부르면 종료 조건이 있어도 못 만납니다.
얼마나 깊어지는가. 수만 번 깊어질 수 있으면 반복문으로 바꿉니다.

정리

재귀는 큰 문제를 한 단계 작은 같은 문제로 바꾸는 것입니다.
더 줄일 수 없는 지점이 종료 조건입니다. 없으면 StackOverflowException 으로 죽습니다.
호출할 때마다 자리가 쌓이고, 값을 돌려줄 때 반대 순서로 풀립니다.
쌓이는 자리에는 한계가 있습니다. 무한 루프와 달리 프로그램이 죽습니다.
단순히 줄어드는 문제는 반복문이 낫습니다. 재귀는 갈래가 뻗는 구조에 어울립니다.
피보나치처럼 같은 값을 다시 계산하는 재귀는 짧지만 아주 느립니다.
종료 조건이 있는가, 매번 가까워지는가, 얼마나 깊어지는가를 확인합니다.