【フィボナッチで遊ぼう】C言語でfor文・再帰・メモ化を比べる｜Python版も補足で紹介 | UNIX Cafe

2026年7月24日

プログラミングを学んでいると、よく登場する数列に フィボナッチ数列 があります。

フィボナッチ数列は、0、1、1、2、3、5、8 のように続く数列です。ルールはとても単純で、前の2つの数を足すと、次の数になるだけです。

今回は、このフィボナッチ数列を C言語 で遊びながら見ていきます。まずは for 文で順番に作り、次に関数化し、再帰、メモ化、隣り合う数の比まで進みます。

最後に、同じ考え方を Python で書くとどう表せるかも補足します。この記事ではC言語を主役にして、Pythonは見比べるための別表現として扱います。

フィボナッチ数列ってなに？

フィボナッチ数列は、最初の2つの数を決めておき、そのあとは前の2つを足して作る数列です。

番号	値	作り方
fib(0)	0	最初の数
fib(1)	1	次の数
fib(2)	1	0 + 1
fib(3)	2	1 + 1
fib(4)	3	1 + 2
fib(5)	5	2 + 3
fib(6)	8	3 + 5

ここでは、fib(0) = 0、fib(1) = 1 として始めます。

このあとに出てくる fib(n) は、「n 番目のフィボナッチ数」という意味です。

基本ルール

今回のルールを、コードで考えやすい形にするとこうなります。

fib(0) は 0
fib(1) は 1
fib(2) 以降は、ひとつ前とふたつ前を足す
大きな番号になるほど、値もすぐ大きくなる

C言語では、前の2つの数を変数に覚えさせながら進めると書きやすいです。

その1：for文で順番に作る

まずは一番わかりやすい方法から始めます。

a にひとつ前の数、b に次の数を覚えさせます。表示したあとで、a と b を少しずつ右へずらしていきます。

fibonacci_loop.c という名前で、次のコードを作ってみます。

#include <stdio.h>

int main(void) {
    int count = 11;
    int a = 0;
    int b = 1;

    for (int i = 0; i < count; i++) {
        printf("fib(%d) = %d\n", i, a);

        int next = a + b;
        a = b;
        b = next;
    }

    return 0;
}

#include <stdio.h>

int main(void) {
    int count = 11;
    int a = 0;
    int b = 1;

    for (int i = 0; i < count; i++) {
        printf("fib(%d) = %d\n", i, a);

        int next = a + b;
        a = b;
        b = next;
    }

    return 0;
}

main関数の読み方

このコードの肝は、a、b、next の3つです。

a は、いま表示するフィボナッチ数を覚えています
b は、その次に使う数を覚えています
next = a + b; で、次のフィボナッチ数を作ります
a = b; と b = next; で、覚えている数をひとつ先へ進めます

for 文は、i = 0 から始まり、i < count の間だけ繰り返します。count を変えると、表示する個数を変えられます。

実行してみる

macOSやLinuxのターミナルなら、次のようにコンパイルして実行できます。

gcc -std=c99 fibonacci_loop.c -o fibonacci_loop
./fibonacci_loop

gcc -std=c99 fibonacci_loop.c -o fibonacci_loop
./fibonacci_loop

実行結果は次のようになります。

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55

その2：関数にしてfib(n)を作る

次は、フィボナッチ数を求める部分を関数にします。

fib(6) と書いたら 8 が返ってくるようにすると、あとから使い回しやすくなります。

fibonacci_function.c という名前で、次のコードを作ってみます。

#include <stdio.h>

int fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }

    int a = 0;
    int b = 1;

    for (int i = 2; i <= n; i++) {
        int next = a + b;
        a = b;
        b = next;
    }

    return b;
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("fib(%d) = %d\n", i, fib(i));
    }

    return 0;
}

#include <stdio.h>

int fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }

    int a = 0;
    int b = 1;

    for (int i = 2; i <= n; i++) {
        int next = a + b;
        a = b;
        b = next;
    }

    return b;
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("fib(%d) = %d\n", i, fib(i));
    }

    return 0;
}

関数の読み方

fib 関数は、n 番目のフィボナッチ数を返す関数です。

最初に n == 0 と n == 1 を調べています。この2つは、足し算で作る前に決まっている特別な値です。

for (int i = 2; i <= n; i++) は、2 番目から n 番目まで順番に作るループです。最後に return b; で答えを返します。

C言語では、関数は呼び出す前に定義しておくか、先に「こういう関数があります」と宣言しておく必要があります。ここでは main 関数より前に fib 関数を書いています。

実行してみる

gcc -std=c99 fibonacci_function.c -o fibonacci_function
./fibonacci_function

gcc -std=c99 fibonacci_function.c -o fibonacci_function
./fibonacci_function

実行結果は、先ほどと同じです。

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55

その3：再帰で書く

フィボナッチ数列は、再帰とも相性がよい題材です。

再帰は、関数の中で同じ関数を呼び出す書き方です。フィボナッチ数列のルールを、そのままコードに近い形で書けます。

fib(n) = fib(n - 1) + fib(n - 2)

fib(n) = fib(n - 1) + fib(n - 2)

fibonacci_recursive.c という名前で、次のコードを作ってみます。

#include <stdio.h>

int fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }

    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("fib(%d) = %d\n", i, fib(i));
    }

    return 0;
}

#include <stdio.h>

int fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }

    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("fib(%d) = %d\n", i, fib(i));
    }

    return 0;
}

関数の読み方

このコードでは、fib 関数の中から、もう一度 fib 関数を呼び出しています。

n == 0 と n == 1 は、そこで計算を止めるための条件です。これがないと、fib(-1)、fib(-2) のように終わらない方向へ進んでしまいます。

return fib(n - 1) + fib(n - 2); は、フィボナッチ数列のルールをそのまま書いている部分です。見た目は短くてきれいですが、あとで見るように同じ計算を何度も繰り返します。

実行してみる

gcc -std=c99 fibonacci_recursive.c -o fibonacci_recursive
./fibonacci_recursive

gcc -std=c99 fibonacci_recursive.c -o fibonacci_recursive
./fibonacci_recursive

小さい値なら、再帰版でもすぐに結果が出ます。

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55

再帰が遅くなる理由

再帰版は短く書けますが、番号を大きくすると急に遅くなります。

たとえば fib(5) を求めるとき、内部では次のように分かれていきます。

fib(5)
= fib(4) + fib(3)
= fib(3) + fib(2) + fib(2) + fib(1)

fib(5)
= fib(4) + fib(3)
= fib(3) + fib(2) + fib(2) + fib(1)

ここで fib(3) や fib(2) が何度も出てきます。つまり、すでに計算したはずの答えを、もう一度計算してしまいます。

fib(10) くらいなら問題ありませんが、fib(40) 以上をそのまま再帰で試すと、環境によってはかなり時間がかかります。この記事では、重い実行例は扱いません。

その4：メモ化で速くする

再帰の形を残しつつ速くしたいときは、メモ化 を使えます。

メモ化は、一度計算した答えを配列に保存しておき、同じ計算が出てきたら保存済みの答えを使う方法です。

fibonacci_memo.c という名前で、次のコードを作ってみます。

#include <stdio.h>

#define MAX_N 50

long long memo[MAX_N + 1];

long long fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (memo[n] != -1) {
        return memo[n];
    }

    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main(void) {
    for (int i = 0; i <= MAX_N; i++) {
        memo[i] = -1;
    }

    for (int i = 0; i <= 20; i++) {
        printf("fib(%d) = %lld\n", i, fib(i));
    }

    return 0;
}

#include <stdio.h>

#define MAX_N 50

long long memo[MAX_N + 1];

long long fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (memo[n] != -1) {
        return memo[n];
    }

    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main(void) {
    for (int i = 0; i <= MAX_N; i++) {
        memo[i] = -1;
    }

    for (int i = 0; i <= 20; i++) {
        printf("fib(%d) = %lld\n", i, fib(i));
    }

    return 0;
}

関数の読み方

memo は「計算済みノート」のような配列です。

最初に memo[i] = -1; としているのは、「まだ計算していない」という印を入れるためです。フィボナッチ数は 0 以上なので、-1 を未計算の印として使えます。

if (memo[n] != -1) は、すでに答えがあるかを調べています。答えがあるなら、もう計算せずに return memo[n]; で返します。

long long は、int より大きな整数を入れられる型です。フィボナッチ数はすぐ大きくなるので、ここでは少し余裕を持たせています。

実行してみる

gcc -std=c99 fibonacci_memo.c -o fibonacci_memo
./fibonacci_memo

gcc -std=c99 fibonacci_memo.c -o fibonacci_memo
./fibonacci_memo

今回は fib(20) まで表示してみます。

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55
fib(11) = 89
fib(12) = 144
fib(13) = 233
fib(14) = 377
fib(15) = 610
fib(16) = 987
fib(17) = 1597
fib(18) = 2584
fib(19) = 4181
fib(20) = 6765

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55
fib(11) = 89
fib(12) = 144
fib(13) = 233
fib(14) = 377
fib(15) = 610
fib(16) = 987
fib(17) = 1597
fib(18) = 2584
fib(19) = 4181
fib(20) = 6765

3つの方法を比べてみる

ここまでの3つの書き方を比べると、次のようになります。

方法	特徴	向いている場面
for文版	前の2つを覚えて順番に作る	実用的に速く求めたいとき
関数化したfor文版	`fib(n)` として使い回せる	他の処理から何度も呼びたいとき
再帰版	数列の定義に近く、短く書ける	再帰の考え方を学びたいとき
メモ化版	一度計算した答えを保存する	再帰の形を残しつつ速くしたいとき

最初に練習するなら、for文版が一番おすすめです。前の値を覚えて、次の値を作り、変数を更新する流れが見えやすいからです。

再帰版は、コードの見た目はきれいです。ただし、何度も同じ計算をしてしまうので、速さを考えると注意が必要です。

おまけ：隣り合う数の比を見てみる

フィボナッチ数列には、もうひとつ面白い性質があります。

隣り合うフィボナッチ数の比を調べると、だんだん 1.618... に近づいていきます。この値は 黄金比 と呼ばれます。

fibonacci_ratio.c という名前で、次のコードを作ってみます。

#include <stdio.h>

int main(void) {
    long long a = 1;
    long long b = 1;

    for (int i = 2; i <= 15; i++) {
        double ratio = (double)b / a;
        printf("fib(%d) / fib(%d) = %.6f\n", i, i - 1, ratio);

        long long next = a + b;
        a = b;
        b = next;
    }

    return 0;
}

#include <stdio.h>

int main(void) {
    long long a = 1;
    long long b = 1;

    for (int i = 2; i <= 15; i++) {
        double ratio = (double)b / a;
        printf("fib(%d) / fib(%d) = %.6f\n", i, i - 1, ratio);

        long long next = a + b;
        a = b;
        b = next;
    }

    return 0;
}

main関数の読み方

double ratio = (double)b / a; は、割り算の結果を小数で見るための処理です。

C言語では、整数どうしをそのまま割ると整数の割り算になります。そこで (double)b と書いて、b を小数として扱っています。

ここでも、最後の next、a = b;、b = next; は、前の2つの数をひとつ先へ進める処理です。

実行してみる

gcc -std=c99 fibonacci_ratio.c -o fibonacci_ratio
./fibonacci_ratio

gcc -std=c99 fibonacci_ratio.c -o fibonacci_ratio
./fibonacci_ratio

実行結果は次のようになります。

fib(2) / fib(1) = 1.000000
fib(3) / fib(2) = 2.000000
fib(4) / fib(3) = 1.500000
fib(5) / fib(4) = 1.666667
fib(6) / fib(5) = 1.600000
fib(7) / fib(6) = 1.625000
fib(8) / fib(7) = 1.615385
fib(9) / fib(8) = 1.619048
fib(10) / fib(9) = 1.617647
fib(11) / fib(10) = 1.618182
fib(12) / fib(11) = 1.617978
fib(13) / fib(12) = 1.618056
fib(14) / fib(13) = 1.618026
fib(15) / fib(14) = 1.618037

fib(2) / fib(1) = 1.000000
fib(3) / fib(2) = 2.000000
fib(4) / fib(3) = 1.500000
fib(5) / fib(4) = 1.666667
fib(6) / fib(5) = 1.600000
fib(7) / fib(6) = 1.625000
fib(8) / fib(7) = 1.615385
fib(9) / fib(8) = 1.619048
fib(10) / fib(9) = 1.617647
fib(11) / fib(10) = 1.618182
fib(12) / fib(11) = 1.617978
fib(13) / fib(12) = 1.618056
fib(14) / fib(13) = 1.618026
fib(15) / fib(14) = 1.618037

最初は値が大きく動きますが、だんだん 1.618 付近に近づいていくのがわかります。

C言語で書くときの注意点

フィボナッチ数列をC言語で扱うときは、数が大きくなりすぎる点に注意します。

int は大きなフィボナッチ数を入れきれません
long long を使うと少し大きな数まで扱えます
それでも限界はあり、ずっと大きな数を扱えるわけではありません
メモ化で配列を使う場合は、配列の範囲を超えないようにします

今回のメモ化版では MAX_N 50 としているので、fib(50) までを想定しています。もっと大きな n を試すなら、配列サイズと整数型の限界をあわせて考える必要があります。

Pythonで書くとどうなる？

同じfor文版をPythonで書くと、次のようになります。

count = 11
a = 0
b = 1

for i in range(count):
    print(f"fib({i}) = {a}")

    next_value = a + b
    a = b
    b = next_value

count = 11
a = 0
b = 1

for i in range(count):
    print(f"fib({i}) = {a}")

    next_value = a + b
    a = b
    b = next_value

考え方はC言語版と同じです。a と b に前の2つの数を覚えさせ、next_value で次の数を作っています。

Pythonでは、変数の型を int や long long と書かなくても動きます。また、整数が大きくなってもC言語より扱いやすいです。

一方で、C言語では変数の型や配列の大きさを自分で決める必要があります。その分、「どこに値を保存しているか」「いつ値が変わるか」を意識しやすくなります。

改造して遊ぶポイント

サンプルコードを動かせたら、少し値を変えて遊んでみます。

count を 20 や 30 に変えて、どこまで表示できるか見る
再帰版で fib(30) くらいを試し、for文版との違いを見る
メモ化版の MAX_N を変えて、配列サイズの意味を確認する
比を調べるコードで、表示する桁数を %.10f などに変えてみる

ただし、再帰版でいきなり大きな値を指定すると、実行に時間がかかることがあります。まずは小さな値から試すのがおすすめです。

まとめ

フィボナッチ数列は、「前の2つを足す」というシンプルなルールから始められる題材です。

C言語で書くと、前の値を変数に覚える、ループで順番に進める、関数で部品にする、再帰で定義に近づける、メモ化で無駄な計算を減らす、という流れを一気に練習できます。

同じフィボナッチ数列でも、書き方を変えると、読みやすさや速さが変わります。まずは count や n を少しずつ変えて、出力がどう変わるかを眺めてみてください。

C言語の次にUnityやUnreal Engineを学ぶ選択肢

プログラミングスクール比較

TECH STADIUM 極（AI GameDev Academy）の評判は？料金・口コミ・就職支援をプログラミング学習者向けに解説 | UNIX Cafe

2026年6月25日

用途ごとに選ぶ C言語のおすすめ本

入門編

レベル・用途別おすすめ C言語本リスト｜UNIX Cafe

2026年4月23日

よかったらシェアしてね！

URLをコピーしました！

URLをコピーしました！

この記事を書いた人

のい UNIX Cafe マスター

Macintosh Color Classicから始まった旅は、長いWindows時代を経て、Windows10のサポート終了をきっかけにUNIXの世界へ戻ってきました。UNIX Cafeでは、UNIX・Linux・そしてMacな世界を、むずかしい言葉を使わず、物語のように書いています。プログラミングは、アイデアをコンピューターに伝えるための言葉です。簡単な単語と文法を覚えれば、誰でもコマンドを使えます。ぜひ一度、やさしいプログラミングの世界をのぞいてみてください。