C++の再帰を活用してln(N!)の値を求める方法

はじめに

数値Nが与えられたとき、再帰（リカージョン）を用いてln(N!)の値を求める方法を解説します。ここでいうln()とは、自然対数、すなわち底がe（ネイピア数）の対数のことです。

解法の考え方

この問題は、対数の基本的な性質を利用することでシンプルに解くことができます。階乗の対数は、積の対数を対数の和に変換できる性質により、次のように展開できます。

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

つまり、ln(N!)は「1からNまでの各整数の対数の総和」と等しくなります。これを再帰の形で表すと、次の漸化式が成り立ちます。

ln(N!) = ln(N) + ln((N-1)!)

再帰の終了条件は「Nが1以下になったとき」です。この場合、ln(1) = 0 であるため、0を返します。

C++での実装例

#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

コードの解説

factLog関数は、引数nが1以下の場合に0を返すことで再帰を終了します。それ以外の場合は、factLog(n - 1)の戻り値にlog(n)を加算した値を返します。これにより、ln(1) + ln(2) + ... + ln(N)が再帰的に順番に計算されていきます。

例えばN = 3の場合、ln(3!) = ln(6) = ln(2) + ln(3) ≈ 0.6931 + 1.0986 ≈ 1.79176 となり、実行結果と一致します。

まとめ

対数の性質「積の対数は対数の和に等しい」を利用することで、大きな階乗の値を直接計算せずにln(N!)を効率よく求められます。再帰を使った実装はコードが簡潔で、数学的な定義とも対応が分かりやすいのが特徴です。