재귀는 "함수 자신을 다시 호출한다"는 문법보다, 어디서 멈추고 어떻게 더 작은 문제로 줄이는지가 핵심입니다.

• 재귀가 왜 끝나지 않는지 확인하고 싶다
• base case와 recursive case를 어떻게 나눠 읽어야 하는지 다시 보고 싶다
• 반복문으로 바꾸는 게 더 나은 문제인지 판단하고 싶다

숏컷 코드

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

문법

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

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

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

반복문과 비교

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

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

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

체크포인트

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

주의할 점