[C#] 재귀함수(Recursion)

 

1. 재귀함수란?

함수 내부에서 자기 자신을 다시 호출하는 함수를 말한다.
복잡한 문제를 더 작은 문제로 나누어 해결할 때 유용하다.

 

void SayHello(int count) {
    if (count == 0) return;
    Console.WriteLine("안녕하세요!");
    SayHello(count - 1);  // 자기 자신 호출
}

 

 

2. 재귀함수의 구조

모든 재귀함수는 두 가지 구조를 갖는다.

• 기저 조건(Base Case): 재귀를 멈추는 조건
• 재귀 호출(Recursive Call): 자신을 다시 호출하는 부분

int Factorial(int n) {
    if (n == 1) return 1;         // 기저 조건
    return n * Factorial(n - 1);  // 재귀 호출
}

 

 

3. 재귀함수 예시

 

📝팩토리얼

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

Console.WriteLine(Factorial(5)); // 출력: 120

 

📝피보나치 수열

int Fibonacci(int n) {
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

 

📝폴더/트리 구조 탐색 등에도 사용된다 (깊이우선 탐색 등)

 

 

📖 정리

✓ 재귀함수는 자기 자신을 다시 호출하는 함수임
✓ 반드시 종료 조건(기저 조건)이 있어야 무한 호출을 방지할 수 있음
✓ 반복문으로도 구현 가능한 문제지만, 재귀를 쓰면 코드를 간결하게 표현할 수 있음
✓ 단점: 호출이 많아지면 스택 오버플로우가 발생할 수 있음
✓ 재귀는 이해가 어려울 수 있으므로 시각화나 디버깅으로 흐름을 확인하는 것이 좋음