C# 재귀 메서드 호출(Recursion) 완벽 이해하기 – 개념부터 실전 예제까지

C#에서 메서드가 자기 자신을 다시 호출하는 방식을 재귀 메서드 호출(Recursive Method Call)이라고 하며, 이러한 프로그래밍 기법을 재귀(Recursion)라고 부릅니다.

재귀는 복잡한 문제를 동일한 구조의 더 작은 문제로 나누어 해결할 때 매우 유용합니다. 대표적인 활용 예로 팩토리얼 계산, 피보나치 수열, 트리 순회 등이 있으며, 이번 글에서는 거듭제곱 계산을 재귀로 구현하는 방법을 살펴보겠습니다.

재귀의 핵심 원리

재귀 함수는 반드시 두 가지 요소를 포함해야 합니다.

• 종료 조건(Base Case): 재귀 호출이 멈추는 조건으로, 이것이 없으면 무한히 자기 자신을 호출하다가 스택 오버플로(Stack Overflow)가 발생합니다.
• 재귀 호출(Recursive Case): 문제를 더 작은 단위로 줄여가며 자기 자신을 다시 호출하는 부분입니다.

예제: 재귀를 사용한 거듭제곱 계산

아래 코드는 숫자 n의 p제곱을 재귀적으로 계산하는 예제입니다. 지수 p가 0이 아니면 함수가 자기 자신을 호출하며, 호출될 때마다 지수가 1씩 감소하는 것이 핵심입니다.

if (p != 0) {
    return (n * power(n, p - 1));
}

위 코드에서 n은 밑(base)에 해당하는 숫자이고, p는 지수입니다. 재귀 호출이 반복될 때마다 p가 하나씩 줄어들어 결국 종료 조건인 p == 0에 도달하게 됩니다.

전체 실행 코드

using System;
using System.IO;

public class Demo {
    public static void Main(string[] args) {
        int n = 5;
        int p = 2;
        long res;
        res = power(n, p);
        Console.WriteLine(res);
    }

    static long power(int n, int p) {
        if (p != 0) {
            return (n * power(n, p - 1));
        }
        return 1;
    }
}

실행 결과

25

코드 동작 과정 분석

이 예제에서 power(5, 2)가 호출되면 다음과 같은 흐름으로 진행됩니다.

1. power(5, 2) → 5 * power(5, 1) 반환
2. power(5, 1) → 5 * power(5, 0) 반환
3. power(5, 0) → p가 0이므로 1 반환 (종료 조건)

따라서 최종 결과는 5 × 5 × 1 = 25가 됩니다.

재귀 사용 시 주의사항

재귀는 코드를 간결하고 직관적으로 만들어 주지만, 몇 가지 주의할 점이 있습니다.

• 성능 오버헤드: 반복문(loop)보다 메서드 호출 비용이 크기 때문에 깊은 재귀는 성능 저하를 일으킬 수 있습니다.
• 스택 오버플로: 종료 조건이 잘못되거나 재귀 깊이가 너무 깊으면 스택 메모리가 초과되어 런타임 오류가 발생합니다.
• 대안 고려: 간단한 반복 작업이라면 while이나 for 반복문으로 구현하는 것이 더 효율적일 수 있습니다.

정리하면, C#의 재귀 메서드 호출은 자기 자신을 호출하여 문제를 해결하는 강력한 기법이며, 명확한 종료 조건을 설계하는 것이 안전하게 활용하는 핵심입니다.