【C++】n番目のペル数を求める方法｜再帰・反復の2つの実装を解説

ペル数とは

本記事では、整数 n が与えられたときに、その位置にあるペル数 P_n を求める問題を解説します。

ペル数とは、次の漸化式で定義される数列のことです。

P_n = 2 × P_n-1 + P_n-2

最初の2項は以下のように定められています。

• P₀ = 0
• P₁ = 1

この定義に従うと、数列は「0, 1, 2, 5, 12, 29, 70, …」と続いていきます。

解法のアプローチ

この問題は、大きく分けて再帰と反復（ループ）の2つの方法で解くことができます。それぞれ順番に見ていきましょう。

方法1: 再帰を使うアプローチ

漸化式をそのまま関数として表現し、自分自身を呼び出しながら P_n を計算する方法です。

コード例

#include <iostream>

using namespace std;
int pell(int n) {
    if(n <= 2)
        return n;
    return 2*pell(n-1) + pell(n-2);
}
int main() {
    int n = 6; // 与えられた n
    cout << pell(n) << "\n"; // その位置のペル数を出力
    return 0;
}

出力

70

コードの解説

n が 2 以下の場合は n をそのまま返しています。これは P₀=0、P₁=1、P₂=2 となるためです。それ以外の場合は、pell(n-1) と pell(n-2) を再帰的に呼び出し、n が 2 以下になるまで計算を繰り返します。

なお、この素朴な再帰では同じ値を何度も再計算してしまうため、時間計算量は指数オーダー O(2ⁿ) になります。メモ化（結果のキャッシュ）を組み合わせれば O(N) まで改善できる点に注意しましょう。

方法2: 反復（ループ）を使うアプローチ

同じ漸化式を、再帰関数の代わりに for ループで順番に計算していく方法です。

コード例

#include <iostream>

using namespace std;
int main() {
    int n = 6;  // 与えられた n
    int p0 = 0;  // P(n-2) の初期値
    int p1 = 1;  // P(n-1) の初期値
    int pn;      // 求める答え

    if(n <= 2) { // n が 2 以下なら n をそのまま出力
        cout << n << "\n";
    } else {
        for(int i = 2; i <= n; i++) { // 2番目の項から n まで計算
            pn = 2*p1 + p0;
            p0 = p1; // 新しい i では p(n-1) が p(n-2) になる
            p1 = pn; // 新しい i では pn が p(n-1) になる
        }
        cout << pn << "\n";
    }
    return 0;
}

出力

70

コードの解説

このプログラムでは、i = 2 から n まで順に処理を行い、p0（P_n-2）と p1（P_n-1）の値を更新しながら pn を求めていきます。各値を一度だけ計算するため、時間計算量は O(N)、空間計算量も O(1) と非常に効率的です。

まとめ

本記事では、n番目のペル数を求める問題について、再帰と反復の2つのアプローチによるC++プログラムを紹介しました。小さな n であれば再帰でも十分ですが、大きな n を扱う場合は反復（またはメモ化付き再帰）を選ぶことで計算量を大幅に抑えられます。なお、同じロジックは C、Java、Python など他の言語でも同様に実装可能です。