関数

[C言語] 再帰関数でフィボナッチ数列を求めて表示する方法を解説

2025-01-18更新日: 2025-01-18

再帰関数は、関数が自分自身を呼び出すことで問題を解決する手法です。C言語でフィボナッチ数列を求める際に再帰関数を使用することができます。

フィボナッチ数列は、最初の二つの数が0と1であり、その後の数は直前の二つの数の和で定義されます。

再帰関数を用いると、基本ケースとしてnが0または1の場合にそれぞれ0と1を返し、それ以外の場合はn-1とn-2のフィボナッチ数を再帰的に計算してその和を返します。

この方法は簡潔ですが、計算量が多くなるため、大きなnに対しては非効率です。

目次から探す

フィボナッチ数列の概要
フィボナッチ数列を求める再帰関数の実装
フィボナッチ数列を求める再帰関数の最適化
応用例
まとめ

フィボナッチ数列の概要

フィボナッチ数列とは

フィボナッチ数列は、数学やコンピュータサイエンスの分野で広く知られている数列です。

この数列は、最初の2つの数が0と1で始まり、その後の各数が直前の2つの数の和として定義されます。

具体的には、数列は次のように始まります: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

フィボナッチ数列は、自然界や芸術、建築など、さまざまな分野で見られるパターンを説明するために使用されることがあります。

フィボナッチ数列の数学的定義

フィボナッチ数列は、以下のように数学的に定義されます。

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n ≧ 2)

この定義により、フィボナッチ数列の各項は、前の2つの項の合計として計算されます。

この再帰的な定義は、プログラミングにおいても再帰関数を用いて実装する際に非常に役立ちます。

フィボナッチ数列の応用例

フィボナッチ数列は、以下のようなさまざまな分野で応用されています。

分野	応用例
自然界	植物の葉の配置、花びらの数、松かさの螺旋構造などにフィボナッチ数列が見られることがあります。
コンピュータサイエンス	アルゴリズムの設計や解析、データ構造の最適化においてフィボナッチ数列が利用されることがあります。
金融	フィボナッチ数列は、株価の動きや市場のトレンドを分析するためのツールとして使用されることがあります。

これらの応用例は、フィボナッチ数列が単なる数学的な興味を超えて、実際の問題解決に役立つことを示しています。

フィボナッチ数列を求める再帰関数の実装

C言語での再帰関数の基本構造

再帰関数とは、関数が自分自身を呼び出すことで問題を解決する手法です。

C言語における再帰関数の基本構造は以下のようになります。

#include <stdio.h>
// 再帰関数の例
int recursiveFunction(int n) {
    if (n <= 1) {
        return n; // 基本ケース
    } else {
        return recursiveFunction(n - 1) + recursiveFunction(n - 2); // 再帰ケース
    }
}

再帰関数には、必ず終了条件(基本ケース)が必要です。

これにより、無限ループに陥ることを防ぎます。

再帰関数を用いたフィボナッチ数列の実装

フィボナッチ数列を求めるための再帰関数をC言語で実装する方法を以下に示します。

#include <stdio.h>
// フィボナッチ数列を求める再帰関数
int fibonacci(int n) {
    if (n <= 1) {
        return n; // 基本ケース
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // 再帰ケース
    }
}
int main() {
    int n = 10; // 求めたいフィボナッチ数列の項数
    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    return 0;
}

0 1 1 2 3 5 8 13 21 34

このプログラムは、フィボナッチ数列の最初の10項を出力します。

fibonacci関数は、再帰的にフィボナッチ数を計算し、main関数でその結果を表示します。

コードの詳細解説

基本ケース: if (n <= 1) { return n; }

フィボナッチ数列の最初の2つの項(0と1)は、再帰を使わずに直接返します。

これが再帰の終了条件となります。

再帰ケース: return fibonacci(n - 1) + fibonacci(n - 2);

それ以外の項は、前の2つの項の和として計算されます。

この部分が再帰的に関数を呼び出す部分です。

main関数:

main関数では、forループを用いて、指定した項数までのフィボナッチ数を計算し、順に出力しています。

この再帰的なアプローチは、コードがシンプルで理解しやすいですが、計算量が多くなると効率が悪くなるため、最適化が必要になる場合があります。

フィボナッチ数列を求める再帰関数の最適化

再帰関数の効率性の問題

再帰関数を用いてフィボナッチ数列を求める方法は、コードがシンプルで直感的ですが、効率性に問題があります。

特に、同じ計算を何度も繰り返すため、計算量が指数的に増加します。

例えば、fibonacci(5)を計算する際に、fibonacci(3)やfibonacci(2)が複数回計算されます。

このような重複計算は、特に大きな数を求める際にパフォーマンスを著しく低下させます。

メモ化による最適化

メモ化は、再帰関数の効率性を改善するための手法です。

計算済みの結果を保存し、同じ計算を再度行わないようにします。

以下は、メモ化を用いたフィボナッチ数列の実装例です。

#include <stdio.h>
#define MAX 100
// メモ化用の配列
int memo[MAX];
// メモ化を用いたフィボナッチ数列を求める関数
int fibonacci(int n) {
    if (n <= 1) {
        return n; // 基本ケース
    }
    if (memo[n] != -1) {
        return memo[n]; // 既に計算済みの場合
    }
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2); // 計算結果を保存
    return memo[n];
}
int main() {
    int n = 10; // 求めたいフィボナッチ数列の項数
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1; // メモ化配列を初期化
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    return 0;
}

0 1 1 2 3 5 8 13 21 34

このプログラムは、メモ化を用いることで、計算済みのフィボナッチ数を再利用し、効率的に数列を求めます。

ループを用いた非再帰的アプローチ

再帰を使わずにループを用いることで、フィボナッチ数列を効率的に求めることもできます。

この方法は、メモリ使用量を抑えつつ、計算を高速化します。

#include <stdio.h>
// ループを用いたフィボナッチ数列を求める関数
void fibonacci(int n) {
    int a = 0, b = 1, c;
    for (int i = 0; i < n; i++) {
        printf("%d ", a);
        c = a + b;
        a = b;
        b = c;
    }
}
int main() {
    int n = 10; // 求めたいフィボナッチ数列の項数
    fibonacci(n);
    return 0;
}