int factorial(int n) {
    if (n < 0) {
        return 0;            /* 이 예제의 입력 범위 밖 */
    }
    if (n == 0) {
        return 1;            /* 종료 조건 */
    }
    return n * factorial(n - 1); /* 더 작은 문제 */
}

문법

재귀 함수는 자기 자신을 다시 호출하는 함수입니다. 읽는 순서는 단순합니다.

• 어디서 멈추는가
• 다음 호출에서 무엇이 더 작아지는가

위 factorial 예시는 n <= 1에서 멈추고, 그 전에는 n - 1로 문제 크기를 줄입니다. 이 둘 중 하나라도 흐리면 재귀는 금방 위험해집니다.

예제의 factorial은 음수 입력을 별도로 정의하지 않았고, 큰 n에서는 반환형 overflow가 먼저 일어납니다. 재귀의 종료 조건은 정상 입력만 멈추게 하는 조건이 아니라, 잘못된 입력을 어떻게 거절할지도 포함해야 합니다.

반복문과 비교

트리 순회나 분할 정복처럼 구조 자체가 자기 닮음이면 재귀가 더 직접적으로 읽힙니다.

void inorder(Node *node) {
    if (node == NULL) {
        return;
    }
    inorder(node->left);
    printf("%d\n", node->value);
    inorder(node->right);
}

반대로 단순 카운터 반복이나 입력 크기가 큰 문제는 반복문이 더 안정적일 수 있습니다. 재귀 호출은 호출할 때마다 새 스택 프레임을 쌓고, 깊이 한도도 환경마다 다르기 때문입니다.

재귀 호출의 시간 복잡도도 따로 셉니다. fib(n - 1) + fib(n - 2)처럼 같은 하위 문제를 여러 번 호출하면 코드가 짧아도 호출 수는 급격히 늘어납니다.

빠른 점검

• base case가 명확해야 합니다.
• 매 호출마다 더 작은 문제로 내려가야 합니다.
• 최대 깊이가 스택에 무리가 없는지 같이 봐야 합니다.
• 트리나 분할 정복처럼 구조가 재귀적일 때 특히 잘 맞습니다.
• 단순 반복은 재귀보다 반복문이 더 안정적일 수 있습니다.

주의할 점