static long Factorial(int n)
{
    if (n < 0) throw new ArgumentOutOfRangeException(nameof(n));
    if (n <= 1) return 1; // 기저 조건
    return checked(n * Factorial(n - 1)); // 더 작은 문제
}

구조

재귀는 함수가 자기 자신을 호출하는 문법보다 문제를 같은 모양의 더 작은 문제로 바꾸는 방식입니다. 핵심은 호출이 반복될수록 반드시 기저 조건에 가까워져야 한다는 점입니다.

먼저 함수 계약을 입력 n의 답을 반환한다처럼 고정한 뒤, 하위 호출도 같은 계약을 만족한다고 가정하고 결과를 조합합니다. 호출 내부 동작을 끝없이 펼치기보다 계약·기저 조건·조합식 세 부분으로 나누어 읽습니다.

static long SumTo(int n)
{
    if (n < 0) throw new ArgumentOutOfRangeException(nameof(n));
    if (n == 0) return 0;
    return n + SumTo(n - 1);
}

이 코드는 아래처럼 쌓였다가 역순으로 풀립니다.

SumTo(3)
  3 + SumTo(2)
      2 + SumTo(1)
          1 + SumTo(0)
              0

각 호출은 지역 변수, 매개변수, 돌아갈 위치를 가진 스택 프레임을 만듭니다. 그래서 재귀 깊이가 깊어지면 시간뿐 아니라 스택 메모리도 사용합니다.

기저 조건이 먼저다

재귀 문제를 풀 때는 호출식을 먼저 쓰기보다 멈추는 조건을 먼저 잡는 편이 안전합니다.

static long Fibonacci(int n)
{
    if (n < 0) throw new ArgumentOutOfRangeException(nameof(n));
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

위 코드는 형태는 단순하지만 같은 값을 반복 계산하므로 시간 복잡도가 급격히 커집니다. 재귀라고 해서 항상 느린 것은 아니지만, 중복 하위 문제가 있는 재귀는 메모이제이션이나 반복 DP로 바꿔야 합니다.

반환형이 long이어도 Fibonacci 값은 결국 overflow합니다. C# long에서는 n <= 92 같은 입력 계약을 두고 checked 연산을 사용하거나, 더 큰 정확한 값이 필요하면 BigInteger와 메모리·시간 비용을 함께 선택합니다.

반복으로 바꾸는 기준

재귀를 반복으로 바꾸면 호출 스택이 명시적인 자료구조로 바뀝니다.

var stack = new Stack<int>();
stack.Push(start);

while (stack.Count > 0)
{
    int current = stack.Pop();
    // current 처리 후 다음 상태 push
}

주의할 점