サイトマップ / Ｃ言語講座＞出入り口＞総目次＞目次：再帰＞フィボナッチ数列を表示する関数（再帰改良版）

フィボナッチ数列を表示する関数（再帰改良版）

[フィボナッチ数列（再帰版）]←このソース→[フィボナッチ数列（動的計画法版）]

/* 前回の関数

前回は、再帰的呼び出しでフィボナッチ数を求めました。そこでは、フィボナッチ数列の定義を素朴にソースプログラムにしました。それを下記に示します。

      // nのフィボナッチ数を返す
    unsigned long Fibo(int n)
    {
        unsigned long f;    // フィボナッチ数をしまう

        switch (n) {
            case 1:
            case 2:                             // n が１か２なら
                f = 1L;                         // f は１
                break;

            default:                            //  それ以外は
                f = Fibo(n - 1) + Fibo(n - 2);  // 再帰呼び出し
                break;
        }
        return (f);                             //  fの値をリターン
    }

しかし、このコードにはまだまだ改善の余地があります。それは、同じFibo( )が何度も呼ばれることです。このことを、オーバーヘッドが大きいといいます。

例えば、Fibo(6)が呼ばれると、Fibo(5)とFibo(4)が呼ばれます。呼ばれた Fibo(5)は、Fibo(4)とFibo(3)を呼びます。呼ばれたもう一方のFibo(4)は、Fibo(3)とFibo(2)を呼びます。結局、同じFibo( )が何度も呼ばれることになります。この様子を下記に示します。

Fibo(6) = Fibo(5) + Fibo(4);

Fibo(6) = (Fibo(4) + Fibo(3)) + (Fibo(3) + Fibo(2));

Fibo(6) = ((Fibo(3) + Fibo(2))) + (Fibo(2) + Fibo(1)))) + ((Fibo(2) + Fibo(1))) + Fibo(2));

Fibo(6) = (((Fibo(2) + Fibo(1)) + Fibo(2))) + (Fibo(2) + Fibo(1)))) + ((Fibo(2) + Fibo(1))) + Fibo(2));

繰り返し呼ばれるので、実行時間がかかります。そこで、何度も同じ計算をしないで済ますため、一度計算したFibo( )の値をresult[ ]という配列に保存し、再利用することで、効率化をはかったのが今回のソースプログラムです。

ソースプログラムの説明

前回と名前の混同を避けるため、関数の名前をFibo2( )とします。

result[ ]は関数の外で宣言します。従って、静的領域に存在し、コンパイル時に０に初期化されます。また、プログラムの実行中常にメモリに存在し、関数から抜け出してもその値は保持されます（静的領域については、変数の記憶クラスと関数や変数のメモリ配置を参照のこと）。そのフィボナッチ数が既に計算済みであればその結果がresult[ ]に保存されています。

Fibo2(n)は呼ばれると、まず、下記の文を実行します。

    if (f = result[n]) 
        return (f);

nのフィボナッチ数が既に計算済みであれば、result[n]は０ではないので真となり、その値を返します。まだ、計算していなければ、 result[n]は０なので、偽となり、フィボナッチ数を計算します。

フィボナッチ数を計算する際、nは４７が限度です。Ｃの配列の添字は０から始まります。result[46]は４７番目になるので、配列のサイズは４７になります。 */

/* ここからソースプログラム */

#include <stdio.h>
#include <stdlib.h>      /* exit(  )で必要 */

unsigned long Fibo2(int n);
void main(void);

#define MAX_VAL 48
unsigned long result[MAX_VAL];    /* ここに計算結果を保存 */

  /* nのフィボナッチ数を返す */
unsigned long Fibo2(int n)
{
    unsigned long f;

	if (f = result[n])        /* フィボナッチ数を計算済みなら */
            return (f);           /* fを返す */
                                  /* まだなら */
    switch (n) {                  /* フィボナッチ数を計算する */
        case 1:
        case 2:                   /* nが１か２なら */
            f = 1L;               /* fは1L */
            break;

        default:                  /* nが２以上なら */
            f = Fibo2(n - 1) + Fibo2(n - 2);    /* 再帰的呼び出し */
            break;
    }
    result[n] = f;               /* データを保存して */
    return (f);                  /* fを返す */
}

void main(void)
{
    int n;        /* nのフィボナッチ数を求める */

    printf("１から４７迄の整数を入力して下さい\t");
    scanf("%d", &n);

    if(n > MAX_VAL - 1) {        /* nが４７より大きければ何もしないで終了 */
        printf("数字が大き過ぎます\n"); 
        exit(0);
    }
      /*  フィボナッチ数を表示 */
    printf("\nFibonacci 数は %lu\n", Fibo2(n));
}

/* ここまでソースプログラム */

/* 前回の再帰版と比べて、実行速度はどうなりましたか。特に、nの値が大きい時に実行速度で大きな差が出たと思います。 */

[フィボナッチ数列（再帰版）]←このソース→[フィボナッチ数列（動的計画法版）]

/* (C) 2000- ＹＦプロ. All Rights Reserved. */    提供：Ｃ言語講座−それ自体コンパイルできる教材を使った講座です−

サイトマップ / Ｃ言語講座＞出入り口＞総目次＞目次：再帰＞フィボナッチ数列を表示する関数（再帰改良版）