2 再帰呼び出しとは

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

これは，実際にプログラムを示した方がよく分かるので，以降に簡単な例を示す．

2.1 階乗の計算

数学で，演算子!で表される階乗という演算にしばしばお目にかかる．たとえば，5の階乗は

$$5! =5\times 4\times 3\times 2\times 1$$

$$=120$$ (1)

である．一般の整数$n$ では，

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

となる．また，$0!=1$ となっている．これらのことから，漸化式は

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

$$0! =1$$ (4)

と表すことができる．

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

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

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

今回の例の場合，再帰呼び出しを使うメリットはほとんど無い．実行速度も繰り返し文を 使うリスト1の方が速いだろうし，メモリーの消費も少ない．し かし，次のハノイの塔のプログラムになると，再帰呼び出しを使うと，簡潔なプログラム が書ける．ここの例題の階乗の計算では，再帰呼び出しのアルゴリズムの大体のイメージ がつかめれば良い．

   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 }

2.2 ハノイの塔

2.2.1 パズルの内容

1883年，フランスの数学者エドゥアール・リュカが考案したパズル「ハノイの塔」の製品 版には，以下の話が書かれていたということである [1]．

世界の中心の地・ベレナスに，天高くそびえる３本のダイヤモンドの柱．そのうち１本に は，64枚の黄金の円盤が刺さっている．向かって左側の柱だ．一番下のものがもっとも大 きく，上に行くにしたがって円盤は小さくなっていく．そうして積み重ねられた64枚の円 盤．これを３つのルールに従って移動していく．

1. 円盤は一度に１枚ずつしか移動できない．
2. 柱のないところに円盤を置いてはならない．
3. 小さい円盤の上に，大きな円盤を重ねてはならない．

そうして右の柱にすべての円盤を移したとき，世界は崩壊し，その終焉を迎えるだろう．

日夜，インドの坊主たちが塔から塔へ円盤を移動させているのである．これが，世界の終 わりの時を刻んでいるというから驚きである．

64枚の円盤を移動させるのは大変なので，3枚の円盤を移動させてみよう．それは，図 3のようになる．

図 3: 円盤が3枚の場合のハノイの塔

2.2.2 パズルの解法

このパズルをC言語のプログラムで解こうというのである．これまでの講義をほとんど完璧 に分かってきた者でも，どのように考えて良いか分からないだろう．しかし，このプログ ラムはびっくりするほど簡単に書けるのである．リスト3を見よ．このパ ズルを解いているところは，関数move()の数行である．びっくりして驚いて，そし てこのプログラムを理解してほしい．

このパズルを解くということは，円盤の移動の手順を示すことである．図 3の左端に書かれている円盤の移動元と移動先を示せれば良い．この手 順をすべて示して，左端にある円盤を右端に移動させるのである．

これを一つずつ考えていたのではとてもプログラムはできない．次にようにすれば，この パズルが完成することが分かるだろう．塔を便宜上，移動元(from)，作業用(work),移動 先(to)に分ける．

1. 移動させるべき円盤が一つの場合，移動元(from)から移動先(to)の塔へ直接移動 させる．
2. 移動させるべき円盤が$n$ 個$(\geq 2)$ の場合
   1. 移送先(to)を作業用に使い，$n-1$ 枚の円盤を移動元(from)から，作 業用(work)へ移動させる．
   2. 移動元(from)の一番下にあった円盤を，移動先(to)へ移動させる．
   3. 移動元(form)を作業用に使い，$n-1$ 枚の円盤を作業用(work)から， 移動先(to)へ移動させる．

これを，階乗を計算したときの漸化式のように記述すると，

• 移動する円盤が一つの場合，移動先の塔へ移動させて処理は終了．
• $n$ 枚の円盤の移動は，

  $$n_{\mathrm{from} \rightarrow\mathrm{to}}= (n-1)_{\mathrm{form}\ri... ...thrm{form}\rightarrow\mathrm{to}}+ (n-1)_{\mathrm{work}\rightarrow \mathrm{to}}$$ (5)

  
  
  と漸化式を書くことができる．

となる．

このアルゴリズムをプログラムで記述したものが，リスト3である．この アルゴリズムとリスト3，および図3を考えよ．

   1 #include <stdio.h>
   2 
   3 /*=====================================================*/
   4 /*  ハノイの塔の移動を示す関数                             */
   5 /*=====================================================*/
   6 void move(int n, char from, char work, char to){
   7 
   8   if(n==1){
   9     printf("%c -> %c\n", from, to);
  10   }else{
  11     move(n-1, from, to, work);
  12     printf("%c -> %c\n", from, to);
  13     move(n-1,work, from, to);
  14   }
  15 }
  16 
  17 /*=====================================================*/
  18 /*  メイン関数                                           */
  19 /*=====================================================*/
  20 int main(){
  21   int n;
  22 
  23   printf("ハノイの塔の円盤の枚数を入力してください\n");
  24   scanf("%d",&n);
  25 
  26   move(n, 'A', 'B', 'C');
  27 
  28   return 0;
  29 }

2.3 クイックソート

実を言うと諸君は，既に再帰呼び出しを使っているのである．リスト 4(教科書 p.8-9 List 1-3)クイックソートの関数は，再帰呼び出し のアルゴリズムとなっている．この関数の動作は単純で，

1. 並べ替えるべき数列の先頭と末尾が，同じか末尾の方が前ならば (if(bottom>=top))ならば，何もしない．並び替えの必要なし．
2. bottom<topならば，その範囲を基準値より大きいものと小さいもの分ける． そして，基準値を大きい組と小さい組の間に入れる．
3. 再帰呼び出しにより，小さい組で同じ処理をする(26行目)．
4. 再帰呼び出しにより，大きい組で同じ処理をする(27行目)．

となっている．

リスト4 クイック ソートの関数(転載について)

   1 void QuickSort(int bottom,int top,int *data)
   2 {
   3     int lower,upper,div,temp;
   4     if(bottom>=top)
   5         return;
   6     /* 先頭の値を「適当な値」とする */
   7     div=data[bottom];
   8     for(lower=bottom,upper=top;lower<upper;)
   9     {
  10         while(lower<=upper&&data[lower]<=div)
  11             lower++;
  12         while(lower<=upper&&data[upper]>div)
  13             upper--;
  14         if(lower<upper)
  15         {
  16             temp=data[lower];
  17             data[lower]=data[upper];
  18             data[upper]=temp;
  19         }
  20     }
  21     /* 最初に選択した値を中央に移動する */
  22     temp=data[bottom];
  23     data[bottom]=data[upper];
  24     data[upper]=temp;
  25 
  26     QuickSort(bottom,upper-1,data);  /* 数列の前半について，再帰呼び出し */
  27     QuickSort(upper+1,top,data);     /* 数列の後半について，再帰呼び出し */
  28 }

[転載について]
このペー ジ中のリスト4のプロ グラムは，教科書として使用している以下の書籍

書名	プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8
著作者	紀平拓男・春日伸弥
出版社	ソフトバンク　パブリッシング株式会社

から転載しました．この転載に関しては，著者と版元に許諾を得ています．

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