2 再帰関数

2.1 再帰関数の例

自分自身を呼び出す関数を再帰関数(recursive function)という．また，自分自身 を呼び出すことを再帰呼出し(recursive call)という．具体的な例をもって説明す るとわかりやすいだろう．

2.1.0.1 階乗

ここでは，数学で使う階乗の計算を再帰関数で説明する．諸君は，階乗についてまだ学習 していないと思われるので，先に階乗について説明しておく必要があるだろう．例えば， 6の階乗は$6!$と書き，次のように計算する．

$$6!=6\times5\times4\times3\times2\times1=720$$ (1)

ようするに整数の値を1ずつ減らして，1になるまで乗算しているのである．これから, 正の整数を$n$として，階乗には次の性質があることが分かる²．

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

$$1! =1$$ (3)

数学では式(2)を漸化式と呼ぶ．もう少し経てば，諸君は数列 とともに詳しく学習するだろう．

キーボードから整数を入力して，その階乗を表示するプログラムを2つ作成する．ひとつ は再帰関数を使わないで繰り返し文で計算するプログラム，もうひとつは再帰関数を使っ たプログラムである．[注意]これらの二つのプログラムは$12!$までしか計算できない．$13!$以上は， 整数型の変数のサイズを越えるからである．

2.1.0.2 繰り返し文による階乗の計算プログラム

リスト1のよ うにすれば階乗の計算ができる．このプログラムの動作は，容易に想像がつくだろう．そ して，作ることもできるだろう．

   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   int i, p=1;
  21 
  22   for(i=n; 1<=i; i--){
  23     p=p*i;
  24   }
  25 
  26   return p;
  27 }

12
12!=479001600

2.1.0.3 再帰関数による階乗の計算プログラム

リスト2のよ うにしても階乗の計算ができる．このプログラムの動作は，なかなか想像がつかないと思 うが，式(2)と式(3)の通りにプログラムして いることに気がついてほしい．これらの式のうち2をプログラ ムすると，関数の中で自分自身を呼び出すことになる．このように自分自身を呼び出す関 数を再帰関数と呼ぶ．

   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

2.2 再帰関数の書き方

再帰関数を使ったプログラムは，アルゴリズムさえ分かれば比較的簡単に記述できる．式 (3)に示したように，漸化式の通りにプログラムを書けば良いのであ る．それでは，漸化式とは何か?--と問いたくなる．漸化式とは「隣同士の関係により数 列の性質を表す式」といえるだろう．ちょっと難しいかなー．例えば，先ほど示した階乗 の数列は，

$$1!,\,2!,\,3!,\,4!,\,5!,\,6!,\,7!,\,8!,\,\cdots,\,(n-1)!,\,n!,\,\cdots$$ (4)

である．隣との関係--すなわち漸化式--は，

$$n!=n\times(n-1)!$$ (5)

である．この通りプログラムを書けば再帰関数を使うことになる．

分割統治法 [2]というアルゴリズムから再帰関数を 考えることもできる．問題を2つ以上の部分に分けて，それぞれを解く．そしてそれを合 わせたもの³が元の問題の 解となる場合である．分けられた問題は元の問題よりも小さくなり，さらに分割できる． そして，自明な解になるまで分割する方法である．先ほど示した$n!$の階乗の計算では， $n$の計算と$(n-1)!$の計算に問題を分けることができる．すなわち

$$n!=n\times(n-1)!$$ (6)

である．このように問題を分けることにより再帰関数が表れる．この通りにプログラムを 書くのである．

再帰関数を使うときに，再帰を終了させる条件を絶対に忘れてはならない．先ほどの階乗 の計算では，

	if(n==1){
	  return 1;
	}

が終了条件となっている．この文により，nが1になれば関数の呼び出しを行わない． この終了の動作の記述を忘れると，プログラムは止まらない．そしてメモリーを使いつづ けるので，いずれはクラッシュして止まる．

再帰関数は難しい概念であるが，非常に便利な場合がある．問題のときかたのアルゴリズ ムは分からないが，分割統治法あるいは漸化式が分かっている場合，解を求めるプログラ ムができてしまう．このような代表例が「ハノイの塔」と呼ばれるパズルである．これに ついては，ちょっとばかり難しいのでこの授業では取り上げないが，興味のある者は私のwebでも見よ．

2.3 再帰関数を使うべきか?

再帰関数と繰り返し文のどちらを使ってもプログラムがかける場合，どちらを使うべきだ ろうか? 両方使える場合は繰り替えし文を使うべきである．計算速度も早いし，メモリー の消費も少ないからである．

単純な問題であれば繰り替えし文の方が良いが，複雑な問題となると再帰関数で記述はで きるが，繰り替えし文ではプログラムが大変困難な場合がある．先ほど少し述べた「ハノイ の塔」や後で学習する「クイックソート」の場合である．このような時には再帰関数を使 い，問題をあざやかに解くことができる．

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