[C언어 50강] 17강. 재귀 함수: 동작 원리, 종료 조건, 대표 예제

Last updated on 
[C언어 50강] 17강. 재귀 함수: 동작 원리, 종료 조건, 대표 예제

재귀 함수는 “함수가 자기 자신을 다시 호출한다”는 문장 하나로 자주 소개되지만, 실무에서 중요한 건 문장 정의가 아니라 호출 스택과 종료 조건을 설계하는 능력입니다. 오늘은 재귀를 단순 암기 대신, 컴퓨터가 실제로 무엇을 쌓고 무엇을 되돌리는지 중심으로 이해해보겠습니다.

핵심 개념

  • 재귀는 문제를 “더 작은 같은 형태의 문제”로 분해하는 사고 방식이며, 함수 호출 스택을 이용해 상태를 자동 저장한다.
  • 재귀 함수는 반드시 종료 조건(base case) 이 있어야 하며, 각 호출이 종료 조건 쪽으로 수렴해야 한다.
  • 재귀는 표현력이 높지만 호출 오버헤드와 스택 한계가 있으므로, 깊이가 깊어질 수 있는 문제는 반복문/명시적 스택 대안을 함께 검토해야 한다.

개념 먼저 이해하기

재귀를 처음 배울 때 가장 많이 생기는 오해는 “함수가 자기 자신을 부르는 마법”처럼 받아들이는 것입니다. 하지만 컴퓨터 관점에서 보면 재귀는 전혀 마법이 아닙니다. 그냥 일반 함수 호출이 여러 번 연속해서 일어나는 것뿐입니다. 차이는 호출 대상이 같은 함수라는 점뿐이고, 나머지는 동일합니다. 호출이 일어날 때마다 매개변수, 지역 변수, 복귀 주소(return address)가 스택 프레임으로 저장됩니다. 그래서 재귀를 이해하려면 문법보다 스택 프레임이 쌓이고(pop/push) 되돌아오는 과정을 머릿속에서 그릴 수 있어야 합니다.

예를 들어 fact(4)를 호출했다고 가정해봅시다. 함수는 fact(3), fact(2), fact(1) 순으로 더 작은 문제를 계속 호출합니다. 이 구간을 흔히 “내려간다”라고 표현합니다. 이때 각 호출은 아직 계산을 끝내지 못한 상태로 스택에 대기합니다. 그러다가 fact(1)에서 종료 조건을 만나 1을 반환하면, 그제야 대기하던 호출들이 역순으로 계산을 완료합니다. 즉 재귀는 문제를 쪼개는 전진 단계 + 결과를 조합하는 복귀 단계가 분리되어 있다는 점이 핵심입니다.

종료 조건은 단순히 “하나 넣어두는 if문”이 아닙니다. 재귀의 생명줄입니다. 종료 조건이 없거나, 있어도 호출 인자가 종료 조건으로 가까워지지 않으면 무한 재귀로 즉시 터집니다. 보통은 스택 오버플로우로 프로그램이 비정상 종료됩니다. 그래서 재귀 설계의 체크리스트는 항상 동일합니다. (1) 종료 조건이 명확한가? (2) 한 번 호출할 때마다 문제가 더 작아지는가? (3) 결국 종료 조건에 도달한다는 걸 논리적으로 설명할 수 있는가?

또 하나 중요한 관점은 재귀가 “항상 더 좋은 해법”은 아니라는 점입니다. 재귀는 트리 순회, 디렉터리 탐색, 분할정복처럼 구조 자체가 재귀적인 문제에서 매우 자연스럽습니다. 반대로 단순 합계, 카운팅, 선형 탐색 같은 문제는 반복문이 더 직관적이고 메모리 사용도 안정적입니다. 실무에서는 읽기 쉬운 구현을 우선하되, 입력 규모가 커질 때 스택 깊이 한계를 넘을 수 있는지 반드시 확인합니다.

마지막으로 재귀를 디버깅할 때는 “현재 호출 깊이(depth)”와 “현재 매개변수 값”을 함께 기록하는 습관이 효과적입니다. 출력 로그 앞에 깊이를 들여쓰기하거나, 함수 진입/복귀를 모두 출력하면 어디서 종료 조건을 놓쳤는지 빠르게 찾을 수 있습니다. 재귀는 겉보기엔 짧은 코드지만 실행 흐름은 길어지기 쉽기 때문에, 시각화 가능한 디버깅 습관이 성패를 가릅니다.

기본 사용

예제 1) 최소 동작 예제: 팩토리얼

#include <stdio.h>

long long factorial(int n) {
    if (n <= 1) {
        return 1;  // 종료 조건
    }
    return (long long)n * factorial(n - 1); // 문제 축소
}

int main(void) {
    for (int i = 1; i <= 5; ++i) {
        printf("%d! = %lld\n", i, factorial(i));
    }
    return 0;
}

설명:

  • n <= 1이 종료 조건입니다. 이 분기가 없으면 함수는 끝나지 않습니다.
  • factorial(n - 1) 호출로 문제가 1씩 작아지므로 종료 조건에 도달할 수 있습니다.
  • 데이터 타입은 int 대신 long long을 써도 빠르게 범위를 넘습니다. 즉, 재귀 문제는 로직뿐 아니라 값 범위도 함께 검토해야 합니다.

예제 2) 실무에서 자주 맞닥뜨리는 패턴: 배열 합 재귀로 표현

#include <stdio.h>

long long sum_array_recursive(const int *arr, int n) {
    if (arr == NULL || n <= 0) {
        return 0; // 실패/빈 배열 처리
    }
    if (n == 1) {
        return arr[0];
    }
    return arr[n - 1] + sum_array_recursive(arr, n - 1);
}

int main(void) {
    int data[] = {3, 1, 4, 1, 5, 9};
    int len = (int)(sizeof(data) / sizeof(data[0]));

    printf("sum = %lld\n", sum_array_recursive(data, len));
    return 0;
}

설명:

  • 배열 합은 반복문이 일반적으로 더 효율적이지만, 재귀 사고 훈련에 좋은 예제입니다.
  • 종료 조건을 두 단계로 나눠(n<=0, n==1) 경계값을 명확히 하면 버그를 줄일 수 있습니다.
  • 실무에선 입력 크기가 매우 클 수 있으므로, 같은 로직이라도 반복문 버전으로 교체 가능한지 항상 고려합니다.

예제 3) 디버깅 포인트 포함 예제: 문자열 길이 계산

#include <stdio.h>

int strlen_recursive_debug(const char *s, int depth) {
    if (s == NULL) {
        printf("[depth=%d] NULL pointer\n", depth);
        return 0;
    }

    printf("[depth=%d] enter: '%c'\n", depth, *s ? *s : '#');

    if (*s == '\0') {
        printf("[depth=%d] base case reached\n", depth);
        return 0;
    }

    int result = 1 + strlen_recursive_debug(s + 1, depth + 1);
    printf("[depth=%d] return: %d\n", depth, result);
    return result;
}

int main(void) {
    const char *text = "C-Recursion";
    int len = strlen_recursive_debug(text, 0);
    printf("length = %d\n", len);
    return 0;
}

설명:

  • depth 인자를 추가하면 호출 깊이를 눈으로 추적할 수 있습니다.
  • s + 1은 다음 문자 주소로 이동합니다. 문자열 끝의 \0을 만났을 때 종료합니다.
  • 재귀 디버깅은 “들어갈 때 로그 + 돌아올 때 로그”를 둘 다 찍어야 흐름이 보입니다.

자주 하는 실수

실수 1) 종료 조건을 빼먹거나 너무 늦게 검사

  • 원인: “어차피 n이 줄어드니까 끝나겠지”라는 막연한 가정.
  • 해결: 함수 시작부에서 종료 조건을 먼저 검사하는 습관을 들입니다. 경계값(0, 1, NULL)을 테스트 케이스로 고정하세요.

실수 2) 문제를 줄이지 않고 같은 인자로 다시 호출

  • 원인: f(n) 내부에서 실수로 f(n)을 다시 호출하는 코드 작성.
  • 해결: 코드 리뷰 시 “재귀 호출 인자가 이전보다 작아지는가?” 항목을 체크리스트로 강제합니다.

실수 3) NULL/음수 같은 비정상 입력 미처리

  • 원인: 정상 입력만 가정하고 함수 계약을 명시하지 않음.
  • 해결: 함수 주석에 입력 제약을 명시하고, 방어 코드를 추가합니다. 필요하면 에러 코드를 반환하세요.

실수 4) 재귀가 더 우아하다는 이유로 무조건 사용

  • 원인: 가독성만 보고 성능·안정성을 검토하지 않음.
  • 해결: 최대 호출 깊이를 추정하고, 깊이가 커질 수 있는 경우 반복문 또는 명시적 스택으로 전환합니다.

실무 패턴

  • 재귀 계약서 작성: 함수 상단 주석에 종료 조건, 입력 범위, 반환 의미를 먼저 씁니다.
  • 경계값 테스트 자동화: 최소 입력(0, 1, 빈 문자열, NULL)을 단위 테스트에 고정합니다.
  • 하이브리드 전략: 데이터가 작을 때는 재귀, 일정 깊이 이상이면 반복/스택으로 전환하는 방식을 고려합니다.
  • 디버깅 가드: 개발 단계에서는 depth 로그를 켜고, 배포 빌드에서 비활성화할 수 있게 매크로를 둡니다.
  • 복잡도 의식: 재귀식이 같은 하위 문제를 중복 계산하면 메모이제이션(캐시) 도입 여부를 검토합니다.

오늘의 결론

한 줄 요약: 재귀의 본질은 자기호출이 아니라 종료 조건까지 안전하게 수렴하도록 문제를 축소하고, 스택 복귀 단계에서 결과를 조합하는 설계 능력입니다.

연습문제

  1. power(base, exp)를 재귀로 구현하세요. 단, exp < 0 입력은 실패로 처리하는 정책을 직접 정의해보세요.
  2. 정수 배열에서 최댓값을 재귀로 찾는 함수를 작성하고, 빈 배열 입력 시 반환 정책(에러 코드/기본값)을 설명해보세요.
  3. 문자열이 회문(palindrome)인지 재귀로 판별하는 함수를 작성하세요. 대소문자 구분 여부를 옵션으로 확장해보면 더 좋습니다.

이전 강의 정답

지난 16강(헤더 파일과 모듈화) 연습문제 예시 정답입니다.

  1. string_utils.h/.c 분리 구현 핵심
  • string_utils.h에는 함수 선언만 둡니다.
  • string_utils.c에는 실제 구현을 둡니다.
  • main.c는 헤더만 include하고 함수 사용.
  1. include guard 누락 재현 결과
  • guard 없는 헤더를 여러 경로로 include하면 타입 재정의 오류가 발생할 수 있습니다.
  • #ifndef/#define/#endif를 추가하면 중복 포함이 차단되어 오류가 사라집니다.
  1. 공개 API 2개 + 내부 static 함수 2개 예시
  • 공개 API: counter_reset, counter_next
  • 내부 static: sanitize_step, clamp_value
  • 핵심은 “외부에 필요한 최소 표면만 공개”입니다.

참고 코드:

/* string_utils.h */
#ifndef STRING_UTILS_H
#define STRING_UTILS_H

void to_upper_ascii(char *s);
int count_vowels(const char *s);

#endif

/* string_utils.c */
#include "string_utils.h"

static int is_vowel_ascii(char c) {
    return c=='a'||c=='e'||c=='i'||c=='o'||c=='u'
        || c=='A'||c=='E'||c=='I'||c=='O'||c=='U';
}

void to_upper_ascii(char *s) {
    if (!s) return;
    for (int i = 0; s[i] != '\0'; ++i) {
        if (s[i] >= 'a' && s[i] <= 'z') s[i] = (char)(s[i] - 'a' + 'A');
    }
}

int count_vowels(const char *s) {
    if (!s) return 0;
    int cnt = 0;
    for (int i = 0; s[i] != '\0'; ++i) {
        if (is_vowel_ascii(s[i])) ++cnt;
    }
    return cnt;
}

실습 환경/재현 정보

  • 컴파일러: Apple clang 17.x 이상 또는 gcc 13+
  • 컴파일 옵션: -std=c11 -Wall -Wextra -Werror -O0
  • 실행 환경: macOS(arm64) 터미널, Linux(x86_64)에서도 동일 재현 가능
  • 재현 체크:
    • factorial(1), factorial(5)가 예상값을 출력하는지 확인
    • 종료 조건을 일부러 제거했을 때 비정상 종료(스택 오버플로우)가 발생하는지 확인
    • 디버그 로그에서 enter/return 순서가 LIFO(후입선출)로 나타나는지 확인