【C言語】フィボナッチ数列生成：再帰・反復・メモ化実装比較を解説

#include <stdio.h>
// 再帰的にフィボナッチ数を計算する関数
int fibRecursive(int n) {
    // 基本ケース：nが0または1の場合はその値を返す
    if (n == 0) return 0;
    if (n == 1) return 1;
    // 再帰呼び出し：前の2項の和を計算する
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}
int main(void) {
    int n = 10;  // 計算したいフィボナッチ数の位置
    // n番目のフィボナッチ数を出力
    printf("再帰によるフィボナッチ数列: %d 番目は %d \n", n, fibRecursive(n));
    return 0;
}

再帰によるフィボナッチ数列: 10 番目は 55

#include <stdio.h>
// 反復的にフィボナッチ数を計算する関数
int fibIterative(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int previous = 0;  // fib(0)
    int current = 1;   // fib(1)
    int next = 0;
    // 2番目以降のフィボナッチ数を順に計算
    for (int i = 2; i <= n; i++) {
        next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}
int main(void) {
    int n = 10;  // 計算したいフィボナッチ数の位置
    // n番目のフィボナッチ数を出力
    printf("反復によるフィボナッチ数列: %d 番目は %d \n", n, fibIterative(n));
    return 0;
}

反復によるフィボナッチ数列: 10 番目は 55

#include <stdio.h>
#include <string.h>
// メモ化のための配列サイズ。ここでは十分な大きさを確保する
#define MAX_SIZE 100
// キャッシュ用の配列。初期値は -1 に設定する
int memo[MAX_SIZE];
// メモ化再帰的にフィボナッチ数を計算する関数
int fibMemo(int n) {
    // キャッシュに値がある場合はそれを返す
    if (memo[n] != -1) return memo[n];
    // 再帰呼び出し：nが0または1の場合の基本ケース
    if (n == 0) return memo[n] = 0;
    if (n == 1) return memo[n] = 1;
    // フィボナッチ数を計算し、キャッシュに登録
    memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
    return memo[n];
}
int main(void) {
    int n = 10;  // 計算したいフィボナッチ数の位置
    // キャッシュ配列を初期化(全ての要素を -1 に設定)
    for (int i = 0; i < MAX_SIZE; i++) {
        memo[i] = -1;
    }
    // n番目のフィボナッチ数を出力
    printf("メモ化によるフィボナッチ数列: %d 番目は %d \n", n, fibMemo(n));
    return 0;
}

メモ化によるフィボナッチ数列: 10 番目は 55