Ｃ言語講座：フィボナッチ数列（再帰版）

１３世紀のイタリアの大数学者フィボナッチ（Leonald Fibonacci）は、ウサギが一定の割合で繁殖して増加する様子を表すために、フィボナッチ数列（Fibonacci Series）を考え出しました。今日は、フィボナッチ数列を例にして、関数の再帰的呼び出し（Recursive Call）について学びます。

Fibo(1)、Fibo(2)を例外として、任意の項はその前の２つの項の合計になっています。結局、下記の数列になります。

この数列は古くから不思議な数列として知られていました。アブラナの種からは二葉が出てきます。クローバーは三つ葉です。アケビという植物には、三つ葉アケビと五葉アケビの２種類があります。桜、山茶花、松葉牡丹の花弁は５枚です。もっと花弁の数の多い花でも、花弁の数がフィボナッチ数になっていることが多いです。松ボックリやパイナップルのうろこのような突起の数は、フィボナッチ数になっています。植物の花びらや葉の数、種の数、など、植物に関係のある数は、フィボナッチ数である場合が多いことが知られています。

この式の右辺は、左辺よりひとつ小さいFibo( )と二つ小さいFibo( )からなっています。Fibo(n)を求めるには、自分よりひとつ小さい自分と、二つ小さい自分を呼び出して、合計すればいいわけです。この関数は再帰的に定義するのが自然です。

フィボナッチ数列の定義を、素直にＣのコードにすると、今回のソースプログラムになります。nが大きくなるとフィボナッチ数は非常に大きくなるので、戻り値をunsigned long型にしました。再帰を使うことによって、わかりやすく、かつ、コンパクトなコードを書くことができます。後はソースプログラムのコメントをごらん下さい。 */

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

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

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

  /* 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の値をリターン */
} 

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

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

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

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

/* このプログラムでは、９８までのフィボナッチ数を求めます。９８のフィボナッチ数は、4204349121です。unsigned long型で表すことのできる最大数は、4294967295ですから、９８が限界で、９９のフィボナッチ数はこのプログラムでは求められません。

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

/* フィボナッチ数列

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

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