4 さまざまな関数とライブラリー

4.1 再帰関数とは

関数の定義において，自分自身を呼び出す関数を再帰関数という．具体的には，リスト 4のような階乗を計算する関数である．階乗は，

$$n!=n\times(n-1)\times(n-2)\times(n-3)\times\cdots\times2\times1$$ (1)

であるが，漸化式を使って

$$n! =n\times (n-1)!\qquad( 1\leqq n)$$ (2)

$$0! =1$$ (3)

のように定義することもできる．この漸化式そのものをプログラムにすると，リスト 4のように再帰関数を使うことになる．

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

12
12!=479001600

次の二つのことをおさえれば，再帰関数を書くことができる．

• 再帰関数の終了条件を書く．
• 漸化式のように問題を分割し，その通りにプログラムを書く．ただし，問題の分 割はつぎのようにする．
  • 分割したものを合わせることにより，元の問題となる．
  • 分割したひとつの問題は，元の問題よりも小さい．
  • 分割したひとつの問題は，元の問題と同じ方法で解ける．
  このように分割することにより，ある自明な解--再帰関数の終了条件--まで分 割できる．そうすると問題が解けるのである．

4.2 プログラム例

4.3 2進数への変換

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

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

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

   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

4.4 フィボナッチ数列

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

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

この数列は，

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

となる．漸化式で表すと

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

$$F_0 =1$$ (6)

$$F_1 =1$$ (7)

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

   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
著者: 山本昌志