フィボナッチ数列の出力プログラムに関するレポート

2025年7月24日 2025年7月30日

1. 問題の概要

フィボナッチ数列は、イタリアの数学者レオナルド・フィボナッチによって1202年に『算盤の書』で紹介された数列である1 2。この数列は、隣接する2項の和が次の項になるという特徴を持ち、0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...のように続く1 3。

数学的には以下の漸化式で定義される1 4:

F0=0,F1=1,Fn=Fn−1+Fn−2(n≥2)F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2} \quad (n \geq 2)F0=0,F1=1,Fn=Fn−1+Fn−2(n≥2)

フィボナッチ数列は単なる数学的概念を超えて、自然界の多くの現象に現れることが知られている3 5。例えば、花びらの枚数、植物の螺旋構造、黄金比との関係など、様々な分野で重要な役割を果たしている。特に、隣接するフィボナッチ数の比は、数列が進むにつれて黄金比 φ = (1+√5)/2 ≈ 1.618 に収束する性質を持つ3 6 7。

本課題では、この列を第1項から第n項まで出力するプログラムを、再帰的手法と反復的手法の両方で実装し、それぞれのアルゴリズムの特性を詳細に分析する。

※本ページは、AIの活用や研究に関連する原理・機器・デバイスについて学ぶために、個人的に整理・記述しているものです。内容には誤りや見落としが含まれている可能性もありますので、もしお気づきの点やご助言等ございましたら、ご連絡いただけますと幸いです。

※本ページの内容は、個人的な学習および情報整理を目的として提供しているものであり、その正確性、完全性、有用性等についていかなる保証も行いません。本ページの情報を利用したこと、または利用できなかったことによって発生した損害（直接的・間接的・特別・偶発的・結果的損害を含みますが、これらに限りません）について、当方は一切責任を負いません。ご利用は利用者ご自身の責任でお願いいたします。

2. 実装したコード

2.1 再帰的実装

Python版（再帰）

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_recursive(n):
    """再帰を使ったフィボナッチ数列の実装（メモ化あり）"""
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# メイン処理
n = int(input("フィボナッチ数列を何項目まで表示しますか？: "))

if n < 1:
    print("1以上の整数を入力してください。")
else:
    print(f"\n再帰版フィボナッチ数列 (n={n}):")
    for i in range(1, n + 1):
        print(f"F({i}) = {fibonacci_recursive(i)}")

C言語版（再帰）

#include <stdio.h>

// 再帰を使ったフィボナッチ数列の実装
int fibonacci_recursive(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

int main() {
    int n;

    printf("フィボナッチ数列を何項目まで表示しますか？: ");
    if (scanf("%d", &n) != 1 || n < 1) {
        printf("正の整数を入力してください。\n");
        return 1;
    }

    printf("\n再帰版フィボナッチ数列 (0項目目から %d 項目目まで):\n", n - 1);
    for (int i = 0; i < n; i++) {
        printf("F(%d) = %d\n", i, fibonacci_recursive(i));
    }

    return 0;
}

2.2 反復的実装

Python版（反復）

def fibonacci_iterative(n):
    """反復処理を使ったフィボナッチ数列の実装"""
    if n <= 1:
        return n

    a, b = 0, 1
    for i in range(2, n + 1):
        a, b = b, a + b
    return b

# メイン処理
n = int(input("フィボナッチ数列を何項目まで表示しますか？: "))

if n < 1:
    print("1以上の整数を入力してください。")
else:
    print(f"\n反復版フィボナッチ数列 (n={n}):")
    for i in range(1, n + 1):
        print(f"F({i}) = {fibonacci_iterative(i)}")

C言語版（反復）

#include <stdio.h>

// 反復処理を使ったフィボナッチ数列の実装
int fibonacci_iterative(int n) {
    if (n <= 1) {
        return n;
    }

    int a = 0, b = 1, temp;
    for (int i = 2; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

int main() {
    int n;

    printf("フィボナッチ数列を何項目まで表示しますか？: ");
    if (scanf("%d", &n) != 1 || n < 1) {
        printf("正の整数を入力してください。\n");
        return 1;
    }

    printf("\n反復版フィボナッチ数列 (0項目目から %d 項目目まで):\n", n - 1);
    for (int i = 0; i < n; i++) {
        printf("F(%d) = %d\n", i, fibonacci_iterative(i));
    }

    return 0;
}

3. n=10 の場合の出力結果

両方のアルゴリズムを実行した場合、以下の結果が得られる:

再帰版フィボナッチ数列 (n=10):
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

反復版フィボナッチ数列 (n=10):
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

両アルゴリズムとも同一の正しい結果を出力することが確認できる。

4. アルゴリズムの利点・欠点に関する考察

4.1 時間計算量の比較

4.1.1 再帰的アルゴリズムの時間計算量

再帰的実装の時間計算量は指数関数的である8 9 10 11。具体的には：

時間計算量: O(φⁿ) ≈ O(1.618ⁿ)

この指数関数的な増加は、同じ部分問題が重複して計算されることに起因する8 9 12。例えば、fibonacci_recursive(5)を計算する際、fibonacci_recursive(3)は3回、fibonacci_recursive(2)は5回計算される8 10。

n=30での実測値では、再帰版は約0.18秒、反復版は約0.00007秒を要し、再帰版は反復版の約2661倍の時間を要した。この膨大な時間差は、関数呼び出し回数の指数関数的増加によるものである:

n=5: 再帰版15回 vs 反復版5回（比率3.0）
n=10: 再帰版177回 vs 反復版10回（比率17.7）
n=15: 再帰版1973回 vs 反復版15回（比率131.5）
n=20: 再帰版21891回 vs 反復版20回（比率1094.5）

4.1.2 反復的アルゴリズムの時間計算量

反復的実装は線形時間で動作する12 13 14:

時間計算量: O(n)

これは、各フィボナッチ数を1回ずつ順番に計算するためである12 14。n項目まで計算するためには、正確にn回の基本演算（加算と代入）が必要となる。

4.2 空間計算量の比較

4.2.1 再帰的アルゴリズムの空間計算量

再帰的実装では、関数呼び出しのたびにスタックフレームが積まれる9 15 16:

空間計算量: O(n)

最大再帰深度はnに等しく、各レベルで引数と戻り値のためのメモリが必要となる。深い再帰によりスタックオーバーフローが発生する可能性がある10 15 16 17。

4.2.2 反復的アルゴリズムの空間計算量

反復的実装は定数メモリのみを使用する13 14:

空間計算量: O(1)

前の2つの値（aとb）のみを保持すればよく、入力サイズnに関係なく一定のメモリ使用量である。

4.3 各アルゴリズムの利点と欠点

4.3.1 再帰的アルゴリズム

利点:

可読性と直感性: フィボナッチ数列の数学的定義をそのまま表現している8 18 15
簡潔性: コードが短く、理解しやすい構造である8 18
保守性: 数学的定義の変更に対して柔軟に対応できる

欠点:

計算効率の悪さ: 指数関数的な時間計算量により、大きなnに対して非実用的8 9 10
重複計算: 同じ部分問題を何度も解くため、計算資源の無駄が大きい8 9 12
スタックオーバーフローリスク: 深い再帰によりメモリ不足を引き起こす可能性10 15 16 17
関数呼び出しオーバーヘッド: 各関数呼び出しに15-30CPUサイクルが必要19

4.3.2 反復的アルゴリズム

利点:

計算効率: 線形時間計算量により大きなnに対しても高速12 13 14
メモリ効率: 定数空間計算量により、メモリ使用量が最小13 14
安定性: スタックオーバーフローのリスクがない12 19
実用性: 実際のアプリケーションでの使用に適している12 14

欠点:

可読性の低下: 数学的定義と実装の乖離により理解が困難18 12
実装の複雑さ: 状態管理（a, bの更新）が必要12 14
デバッグの困難さ: ループ内の状態変化を追跡する必要がある

4.4 実用的考慮事項

4.4.1 整数オーバーフローの問題

両アルゴリズムとも、大きなnでは整数の表現範囲を超える問題が発生する20 21。C言語のint型（32bit）では、F(47) = 2,971,215,073あたりでオーバーフローが始まる20。

4.4.2 プログラミング言語による制限

Pythonは任意精度整数をサポートするため、理論上は無制限にフィボナッチ数を計算できるが20 22、C言語では適切なデータ型の選択（long long等）が必要である20 21。

4.4.3 最適化手法の存在

実際の問題解決では、以下の最適化手法が利用可能である:

メモ化（動的計画法）: 計算済みの値を保存し再利用9142324
- 時間計算量: O(n)
- 空間計算量: O(n)
行列の冪乗: 行列演算による高速計算2526
- 時間計算量: O(log n)
ビネットの公式: 一般項による直接計算225
- 時間計算量: O(1)
- ただし浮動小数点演算の精度問題あり

5. 結論

フィボナッチ数列の計算において、再帰的アルゴリズムと反復的アルゴリズムは大きく異なる特性を示す。再帰的実装は数学的定義の直接的な表現として教育的価値が高く、コードの可読性に優れるが、指数関数的な時間計算量とスタックオーバーフローのリスクにより実用性に乏しい。

一方、反復的実装は線形時間計算量と定数空間計算量により、実用的なアプリケーションに適している。大きなnに対しても安定して動作し、メモリ効率も優秀である。

この比較から、アルゴリズム選択における重要な教訓が得られる。理論的な美しさと実用性は必ずしも一致せず、問題の規模と要求される性能に応じて適切な手法を選択することが重要である。また、計算量の理論的分析と実装上の制約の両方を考慮したアルゴリズム設計の重要性も明確になった。

フィボナッチ数列という単純な問題を通じて、アルゴリズムの効率性、実装の複雑さ、可読性のトレードオフを深く理解することができ、これらの知見は他の計算問題への応用においても valuable な指針となる。