3 再帰呼び出し

3.1 再帰呼び出しとは

関数の中で，自分自身の関数を呼び出すことを再帰呼び出し(recursive call)と言う．このアルゴリズムを使うと，ある種の問題に対して，手続きが非常に簡素に表現できることがある．

これは，実際にプログラムを示した方がよく分かるので，簡単な例を示す．数学で，演算子!で表される階乗という演算にしばしばお目にかかる．たとえば，5の階乗は

$\displaystyle 5!$	$\displaystyle =5\times 4\times 3\times 2\times 1$
	$\displaystyle =120$	(1)

である．一般の整数

では，

$\displaystyle n!=n\times (n-1)\times (n-2)\times\cdots\times 2\times 1$

(2)

となる．また，

となっている．これらのことから，漸化式は

$\displaystyle n!$	$\displaystyle =n\times(n-1)!$	(3)
$\displaystyle 0!$	$\displaystyle =1$	(4)

と表すことができる．

ここで，整数を入力して，その階乗を計算するプログラムを作ってみよう．通常は，式 (2)の通りにプログラムを書くだろう．この式の通りにプログラムを書くと，リスト3のようになる．

同じ計算を，式(3)と(4)に着目してプログラムを作ってみよう．すると，リスト4のようになる．このプログラムを見ると，漸化式をそのままプログラムしたことが分かるだろう．

リスト4のプログラムは，リスト3とは異なり，関数内で自分自身を呼びだしている．このように，自分自身を呼び出すことを再帰呼び出し(recursive call)と言う．C言語ではこのように自分自身を呼び出すことができる．

これまでの例で，再帰呼び出しは繰り返し文と似ていることが分かっただろう．繰り返し文では，無限ループにならないように，必ず終了条件が必要であった．同じように，再帰呼び出しでも，呼び出しの終了条件が絶対に必要である．そうしないと，無限に関数を呼び出すことになり，いずれはプログラムがクラッシュするであろう．

もうひとつ重要なことは，再帰呼び出しが出きるようなアルゴリズムを考えなくてはならない．一つの考え方は，漸化式を書いてみることである．数学の漸化式のような考え方ができれば，それを忠実にプログラムすれば，再帰呼び出しができるであろう．

   1 #include <stdio.h>
   2 
   3 /*=====================================================*/
   4 /*  階乗を計算する関数                                    */
   5 /*=====================================================*/
   6 int kaijyo(int n){
   7   int i, value;
   8   
   9   value=1;
  10 
  11   for(i=n; i>=1; i--){
  12     value*=i;
  13   }
  14 
  15   return value;
  16 
  17 }
  18 
  19 /*=====================================================*/
  20 /*  メイン関数                                    */
  21 /*=====================================================*/
  22 int main(){
  23   int n;
  24 
  25   printf("階乗を計算します．値を入れてください\n");
  26   scanf("%d",&n);
  27 
  28   printf("%d!=%d\n",n,kaijyo(n));
  29 
  30   return 0;
  31 }

   1 #include <stdio.h>
   2 
   3 /*=====================================================*/
   4 /*  階乗を計算する関数                                    */
   5 /*=====================================================*/
   6 int kaijyo(int n){
   7 
   8   if(n==0){
   9     return 1;
  10   }else{
  11     return n*kaijyo(n-1);
  12   }
  13 
  14 }
  15 
  16 /*=====================================================*/
  17 /*  メイン関数                                    */
  18 /*=====================================================*/
  19 int main(){
  20   int n;
  21 
  22   printf("階乗を計算します．値を入れてください\n");
  23   scanf("%d",&n);
  24 
  25   printf("%d!=%d\n",n,kaijyo(n));
  26 
  27   return 0;
  28 }