C++で再帰を使って級数1² + 2² + 3² + … + n²の総和を求める方法

本記事では、級数 1² + 2² + 3² + … + n² の第 n 項までの総和を求める問題を取り上げます。数値 n が与えられたとき、この級数の合計を計算するプログラムを C++ で作成します。まず反復処理（ループ）による基本的な解法を確認し、その後、再帰を使った実装方法も詳しく解説します。

問題を理解するための例

入力:

n = 4

出力:

30

説明: sum = (1 × 1) + (2 × 2) + (3 × 3) + (4 × 4) = 1 + 4 + 9 + 16 = 30

アルゴリズム（反復処理）

最もシンプルな解法は、1 から n まで順に各数値の 2 乗を求め、合計変数へ加算していく方法です。

sum = 0 で初期化する
Step 1: i = 1 から n まで繰り返し、以下を実行する
    Step 1.1: sum += i * i で合計を更新する
Step 2: sum を出力する

C++ での実装例（ループ版）

上記のアルゴリズムを実装したプログラムが次のとおりです。

#include <iostream>
using namespace std;

long long calcSeriesSum(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++)
        sum += (long long)i * i;
    return sum;
}

int main() {
    int n = 7;
    cout << "級数 1^2 + 2^2 + 3^2 + ... + " << n << "^2 の総和は "
         << calcSeriesSum(n) << " です";
    return 0;
}

出力:

級数 1^2 + 2^2 + 3^2 + ... + 7^2 の総和は 140 です

再帰を使った実装

続いて、同じ計算を再帰で行う方法を紹介します。再帰では「n の 2 乗」と「n − 1 までの級数の総和」を足し合わせることで答えを導きます。再帰関数は次の 2 つの要素で構成されます。

• 基本ケース: n = 0 のときは項が存在しないため 0 を返す
• 再帰ケース: n × n + calcSeriesSum(n − 1) を返す

#include <iostream>
using namespace std;

long long calcSeriesSumRecursive(int n) {
    if (n == 0)                     // 基本ケース
        return 0;
    return (long long)n * n         // 再帰ケース
         + calcSeriesSumRecursive(n - 1);
}

int main() {
    int n = 7;
    cout << "級数 1^2 + 2^2 + 3^2 + ... + " << n << "^2 の総和は "
         << calcSeriesSumRecursive(n) << " です";
    return 0;
}

出力:

級数 1^2 + 2^2 + 3^2 + ... + 7^2 の総和は 140 です

再帰の動作イメージ（n = 4 の場合）

calcSeriesSumRecursive(4)
= 4×4 + calcSeriesSumRecursive(3)
= 16 + (9 + calcSeriesSumRecursive(2))
= 16 + 9 + (4 + calcSeriesSumRecursive(1))
= 16 + 9 + 4 + (1 + calcSeriesSumRecursive(0))
= 16 + 9 + 4 + 1 + 0
= 30

計算量と実装上の注意点

どちらの実装も各項を一度ずつ計算するため、時間計算量は O(n) です。一方、空間計算量はループ版が O(1) であるのに対し、再帰版は呼び出しスタックを使用するため O(n) となります。n が非常に大きい場合、再帰版ではスタックオーバーフローを起こす可能性がある点に注意しましょう。

また、級数の総和は n が大きくなるにつれて急激に増加し、int 型（最大約 21 億）の範囲を簡単に超えてしまいます。そこで戻り値には long long 型を使用し、オーバーフローを防止しています。