3 再帰関数の例

3.1 2進数

入力された正の整数を2進数で表示するプログラムを書く．これは再帰関数を使って，記 述することができる．10進数から2進数に変換するとき，2で割ってあまりを書く--とい う作業を繰り返したことを思い出してほしい．同じことを繰り返したはずである．

このプログラムを書くためには，2で割った商とあまりの演算が必要である．商の演算に は「/」を，あまりの演算には「%」をつかう．これは整数同士の演算でし ばしば使われるので憶えておく必要がある．

準備はできた．再帰関数を使った2進数への変換プログラムは，リスト3 のようになる．

   1 #include <stdio.h>
   2 
   3 void print_binary(int n);                 // プロトタイプ宣言
   4 
   5 //========== メイン関数 ================================
   6 int main(void)
   7 {
   8   int nx;
   9 
  10   scanf("%d", &nx);                // 整数入力
  11   print_binary(nx);               // 関数呼出し
  12   printf("\n");
  13 
  14   return 0;
  15 }
  16 
  17 //========== 2進数を表示する関数(再帰呼出し)===============
  18 void print_binary(int n)
  19 {
  20 
  21   if(n==0){
  22     return;
  23   }else{
  24     print_binary(n/2);
  25     printf("%d",n%2);
  26   }
  27 
  28 }

1234
10011010010

3.2 フィボナッチ数列

フィボナッチ数列も再帰関数の代表的な問題である．この数列は次のようなものである．

成熟した1つがいのウサギは，1ヶ月後に1つがいのウサギを生むとする．そして，生まれ たウサギは1ヶ月かけて成熟して次の月から毎月1つがいのウサギを生む．全てのウサギ はこの規則に従うとし，死ぬことは無いとする．$n$ヶ月後にウサギはつがいの数は?

この数列は，

$$1,\,1,\,2,\,3,\,5,\,8,\,13,\,21,\,34,\cdots$$ (7)

となる．漸化式で表すと

$$F_n =F_{n-1}+F_{n-2}$$ (8)

$$F_0 =1$$ (9)

$$F_1 =1$$ (10)

である．リスト4にこの数列の計算プログラムを示す．

   1 #include <stdio.h>
   2 
   3 int fibonacci(int n);                 // プロトタイプ宣言
   4 
   5 //========== メイン関数 ================================
   6 int main(void)
   7 {
   8   int month;
   9 
  10   printf("何ヶ月後?\t");
  11   scanf("%d", &month);                         // 整数入力
  12   printf("つがいの数 = %d\n", fibonacci(month));  // 関数呼出し
  13 
  14   return 0;
  15 }
  16 
  17 //========== 2進数を表示する関数(再帰呼出し)===============
  18 int fibonacci(int n)
  19 {
  20 
  21   if(n==0 || n==1){
  22     return 1;
  23   }else{
  24     return fibonacci(n-1)+fibonacci(n-2);
  25   }
  26 
  27 }

何ヶ月後?       8
つがいの数 = 34

ホームページ: Yamamoto's laboratory
著者: 山本昌志