C++ 재귀 함수로 ln(N!) 값 계산하는 방법

문제 개요

어떤 수 N이 주어졌을 때, 재귀(recursion)를 이용하여 ln(N!)의 값을 구하는 것이 목표입니다. 여기서 ln()은 자연로그(natural logarithm), 즉 밑이 e인 로그를 의미합니다.

이 문제는 로그의 곱셈 법칙을 활용하면 간단하게 해결할 수 있습니다. 팩토리얼을 먼저 계산한 뒤 로그를 취하는 대신, 로그를 각 항으로 분리할 수 있다는 점이 핵심입니다.

핵심 공식

$$\ln\lgroup N!\rgroup=\ln\lgroup N*(N-1)*(N-2)*\dotsm*2*1\rgroup=\ln(N)+\ln(N-1)+\dotsm+\ln(1)$$

즉, ln(N!)은 1부터 N까지 각 숫자의 자연로그 값을 모두 더한 것과 같습니다. 이 성질을 이용하면 팩토리얼 값 자체가 매우 커져 오버플로가 발생하더라도 안전하게 결과를 구할 수 있습니다.

구현 아이디어

재귀 함수는 다음과 같은 구조로 작성합니다.

• 기저 조건(Base Case): n이 1 이하이면 ln(1) = 0이므로 0을 반환합니다.
• 재귀 단계: factLog(n-1)의 결과에 현재 값의 로그인 log(n)을 더해 반환합니다.

예제 코드

#include <iostream>
#include <cmath>
using namespace std;
double factLog(int n) {
    if (n <= 1)
        return 0;
    return factLog(n - 1) + log(n);
}
int main() {
    int N = 3;
    cout << factLog(N);
}

실행 결과

1.79176

동작 원리 설명

N = 3일 때 함수는 다음과 같이 동작합니다.

1. factLog(3) → factLog(2) + log(3)
2. factLog(2) → factLog(1) + log(2)
3. factLog(1) → 기저 조건에 도달하여 0 반환

따라서 최종 결과는 log(3) + log(2) + log(1) ≈ 1.0986 + 0.6931 + 0 = 1.79176이 됩니다. 이 코드의 시간 복잡도는 O(N), 공간 복잡도는 재귀 호출 스택으로 인해 O(N)입니다.