再帰を使ってフィボナッチ数列を求めるC++プログラム

フィボナッチ数列は、最初の2項が0と1であり、それ以降の各項が直前の2項の和となる数列です(0, 1, 1, 2, 3, 5, 8, 13, 21...)。この記事では、再帰関数を用いてフィボナッチ数列を生成するC++プログラムを紹介します。

サンプルコード

#include <iostream>
using namespace std;
int fib(int x) {
    if((x==1)||(x==0)) {
        return(x);
    }else {
        return(fib(x-1)+fib(x-2));
    }
}
int main() {
    int x , i=0;
    cout << "Enter the number of terms of series : ";
    cin >> x;
    cout << "\nFibonnaci Series : ";
    while(i < x) {
        cout << " " << fib(i);
        i++;
    }
    return 0;
}

実行結果

Enter the number of terms of series : 15
Fibonnaci Series : 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

プログラムの解説

上記のプログラムでは、フィボナッチ数を計算する本体のコードが関数「fib」に実装されています。

if((x==1)||(x==0)) {
    return(x);
}else {
    return(fib(x-1)+fib(x-2));
}

この関数は再帰的に動作します。引数 x が 0 または 1 の場合はそのまま値を返します(これを基底ケースと呼びます)。それ以外の場合は fib(x-1) と fib(x-2) の和を返すため、フィボナッチ数列の定義 f(n) = f(n-1) + f(n-2) がそのままコードとして表現されています。

main() 関数では、ユーザーから表示したい項数を入力してもらい、while ループの中で fib() を呼び出しながら、先頭の項から順にフィボナッチ数列を出力していきます。

cout << "Enter the number of terms of series : ";
cin >> x;
cout << "\nFibonnaci Series : ";
while(i < x) {
    cout << " " << fib(i);
    i++;
}

注意点：計算量について

この再帰による実装はシンプルで理解しやすい反面、同じ計算を何度も繰り返し行うため非効率です。時間計算量は O(2ⁿ) 程度となり、項数が大きくなると処理に非常に長い時間がかかります。実際の開発では、メモ化(計算結果のキャッシュ)を利用した再帰や、ループによる反復処理(O(n))での実装が推奨されます。