재귀 함수, 값은 도대체 언제 계산될까?

코드는 짧은데 머릿속이 복잡한 이유

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

네 줄입니다. 그런데 factorial(4) 를 눈으로 따라가려 하면 어디까지 계산됐는지 금방 헷갈립니다.

이유가 있습니다. 우리는 코드를 위에서 아래로 읽는데, 재귀는 내려갔다가 다시 올라오기 때문입니다.

한 줄 정의

재귀 함수는 자기 자신을 호출하는 함수이고, 그 호출들은 호출 스택(call stack) 에 차곡차곡 쌓입니다.

핵심은 이겁니다 — 쌓는 동안에는 아무 값도 정해지지 않습니다.

실제로 어떻게 진행되는가

factorial(4) 를 부르면 이렇게 됩니다.

1번부터 3번까지, 세 번을 호출하는 동안 계산된 값은 하나도 없습니다. return n * factorial(n-1) 에서 곱셈을 하려면 오른쪽 값이 필요한데, 그게 아직 없으니 곱셈이 미뤄집니다.

값이 처음 생기는 건 4번 — 기저 조건에 닿았을 때입니다. 그때부터 되돌아오며 하나씩 확정됩니다.

기저 조건을 빠뜨리면

int bad(int n) {
    return n * bad(n - 1);   // 멈추는 조건이 없다
}

이 함수는 영원히 내려갑니다. 프레임이 계속 쌓이고, 스택에 할당된 메모리를 다 쓰면 스택 오버플로(stack overflow) 로 프로그램이 죽습니다.

무한 루프와는 증상이 다릅니다. 무한 루프는 메모리를 안 먹고 계속 돌지만, 무한 재귀는 메모리를 먹다가 터집니다.

재귀 vs 반복

같은 계산을 반복문으로도 쓸 수 있습니다.

int factorial_loop(int n) {
    int r = 1;
    for (int i = 2; i <= n; i++) r *= i;
    return r;
}

이쪽은 곱셈이 즉시 일어납니다. r 에 값이 계속 갱신되니 어느 시점에 봐도 중간 결과가 있습니다. 스택도 한 프레임만 씁니다.

재귀가 항상 낫다는 뜻이 아닙니다. 구조 자체가 재귀적인 문제(트리 순회, 하노이탑, 병합 정렬)에서는 재귀가 코드를 훨씬 짧고 정확하게 만들지만, 팩토리얼 같은 단순 누적은 반복이 낫습니다.

정리

• 재귀는 호출할 때 값을 만들지 않습니다. 기저 조건에 닿아야 되돌아오며 확정됩니다
• 호출마다 스택 프레임이 생기고, 거기에 매개변수·지역변수·돌아갈 주소가 들어갑니다
• 기저 조건은 모든 입력이 반드시 만나도록 범위로 잡아야 합니다
• 무한 재귀는 무한 루프와 달리 메모리를 소모하다 터집니다
• 구조가 재귀적인 문제에 쓰고, 단순 누적은 반복문이 낫습니다

코드가 헷갈렸던 건 어려워서가 아니라, 내려가는 동안 아무 일도 안 일어난다는 걸 몰랐기 때문입니다.