C 재귀 함수 쉽게 이해하기: 작성과 활용

C 재귀 함수 쉽게 이해하기

이 튜토리얼에서는 핵심 개념부터 자연수 합 구하기 실전 예제까지 C 재귀의 기초를 안내합니다.

재귀 함수는 자기 자신을 호출하는 함수입니다. 이 자기 참조 기법인 재귀를 사용하면 문제를 더 작고 동일한 하위 문제로 분해해 해결할 수 있습니다.

재귀 작동 원리

void recurse() {
    /* 사전 처리 */
    recurse();
    /* 사후 처리 */
}
int main() {
    /* 초기 설정 */
    recurse();
    /* 후속 작업 */
}

재귀는 중단 조건(종종 기본 사례라 불림)에 도달할 때까지 반복됩니다. if…else 가드나 유사 구문을 사용해 함수가 결국 종료되도록 보장하고 무한 루프를 방지합니다.

예제: 재귀로 자연수 합 구하기

#include <stdio.h>
int sum(int n);
int main() {
    int number, result;
    printf("양의 정수 입력: ");
    scanf("%d", &number);
    result = sum(number);
    printf("sum = %d", result);
    return 0;
}
int sum(int n) {
    if (n != 0)
        return n + sum(n-1); // 재귀 호출
    else
        return 0; // 기본 사례
}

출력

양의 정수 입력: 3
sum = 6

이 예제에서 sum()은 사용자 입력과 함께 main()에서 호출됩니다. 함수는 n이 0이 될 때까지 감소된 n 값으로 자기 자신을 호출합니다. 기본 사례에서 0 반환 후 재귀 호출이 언와인드되며 각 중간 값이 main()까지 더해집니다.

재귀의 장단점

재귀는 트리 순회, 팩토리얼 계산, 피보나치 수열처럼 재귀적 구조에 자연스럽게 매핑되는 문제에 대해 더 깔끔하고 읽기 쉬운 코드를 산출합니다. 그러나 함수 호출 오버헤드와 호출 스택으로 인한 메모리 사용 증가로 반복 루프보다 느릴 수 있습니다. 성능 중요 코드에서는 반복적 솔루션이나 메모이제이션을 고려하세요.

잠재적 단점에도 불구하고 재귀는 많은 알고리즘과 자료구조 연산의 기초가 되는 컴퓨터 과학의 근본 개념입니다. 재귀를 마스터하면 복잡한 문제를 우아하고 정밀하게 해결할 수 있습니다.