再帰を用いたプログラム

Copyright(C) 14Jan2007 coskx

関数が自分自身を関数として呼び出すことを「再帰」という。
プログラムのあるものは「再帰」を使わないと書けない場合もある。またあるものは再帰を使ったほうが見通しよくプログラミングできる場合もある。

List 10.1.1 再帰導入のためのプログラム

#include <stdio.h> void func4(int n) {     printf("%d\n",n); } void func3(int n) {     printf("%d\n",n);     if (0<n) func4(n-1); } void func2(int n) {     printf("%d\n",n);     if (0<n) func3(n-1); } void func1(int n) {     printf("%d\n",n);     if (0<n) func2(n-1); } int main() {     func1(3);     return 0; } /*** 実行結果 *** 3 2 1 0 ****************/

List 10.1.1は簡単に動作追跡ができる。
同様の動作のプログラムを「自分で自分を呼び出す関数」で作ってみよう。
「自分で自分を呼び出す関数」のことを再帰関数と呼び，このような構造のプログラムを再帰プログラムと呼ぶ。
関数内で使用されるオート変数（引数変数を含む）は，関数が呼び出されるたびに作成され，呼び出し側の変数と混同されることはない。

List 10.1.2 再帰を用いて書きなおしたプログラム

#include <stdio.h> void recfunc(int n) {     printf("%d\n",n);     if (0<n) recfunc(n-1); } int main() {     recfunc(3);     return 0; } /*** 実行結果 *** 3 2 1 0 ****************/

プログラムの動作を図示したところ

再帰関数では，特別の場合にそれ以上自分自身を呼び出さない仕掛けを持たないと無限呼び出しになってしまう。
上記の再帰関数recfunc()では，0<nの場合のみ自分自身を呼び出すことになっており，nは必ず1だけ減って呼び出しているため，無限呼び出しにならないようになっている。

	２．簡単な再帰の例（１からｎまでの和を求める）

1から10までの和を求めるのに関数君に命令したら，実は関数君はめんどくさがり屋で，友人に下請け仕事に出して，自分は簡単な仕事だけで 済ませようとしていた。１からNまでの和を求めなさいといわれたら，1からN-1までの和を隣の人に計算してもらって，自分はその答えにNを加えて答えるというずうずうしさである。

それぞれの関数君は次のように考えていた。

A:「１から１０までの和」を求めるには，「１から９までの和」を求めたものに１０を加えればよい。
　　だからBさんに「１から９までの和」を求めてもらい，自分は１０を加えるだけ。
B:「１から９までの和」を求めるには，「１から８までの和」を求めたものに９を加えればよい。
　　だからCさんに「１から８までの和」を求めてもらい，自分は９を加えるだけ。
C:「１から８までの和」を求めるには，「１から７までの和」を求めたものに８を加えればよい。
　　だから・・・
　　　　　　　　　　　　　　　　　：
H:「１から３までの和」を求めるには，「１から２までの和」を求めたものに３を加えればよい。
　　だから・・・
I:「１から２までの和」を求めるには，「１から１までの和」を求めたものに２を加えればよい。
　　だから・・・
J:「１から１までの和」は１です。

それでも答えは55で正解であった。

どの関数君も作業内容は同じである。

・nの値をもらう。（1からnまでの和を求めるように依頼されたことになる）
・nの値が1であったら，1を依頼元に返す。そうでなかったら次のことを行う。
・つぎの関数君ににn-1の値を与える。（1からn-1までの和を求めるように依頼したことになる）
・つぎの関数君から答えをもらう。（1からn-1までの和をもらったことになる）
・その答えにnを加えて，依頼元に返す。

1人の関数君の作業は単純だがみんなで力を合わせると大きな仕事ができる。

実際のプログラムでは，10人の人間がいるわけではなく，自分の分身に作業をさせるようになっている。

１からｎまでの和を求める関数を作るが，自分自身を引数を１減じて呼び出すように作る。
また，１から１までの和を求める場合には１を返すように特別に設定する。
（特別の場合にそれ以上自分自身を呼び出さない仕掛けを持たないと無限呼び出しになってしまう。）

List 10.2.1 ソースファイルsum.c

#include <stdio.h> int sumup(int n) {     int ret;     if (n==1) { /*無限呼び出しにならない保証*/         ret= 1;     } else {         ret= sumup(n-1)+n;     }     return ret; } int main() {     int sum10;     sum10=sumup(10);     printf("sum up to %d : %d\n",10,sum10);     return 0; }

実行結果

>sum.exe sum up to 10 : 55

再帰の関数を書くときには，どこかで無限呼び出しにならない保証を書いておかなければならない。
この例では，if (n==1) の時はそれ以上再帰呼び出しをしないようにしてある。

再帰関数と関数内変数について

一般に関数内の変数（オート変数）は，呼び出し側関数内にも同じ名前の変数があったとしてもそれは別の変数として扱われる。
再帰関数にしてもこの原理は成り立っているので，呼び出し側と呼び出され側の変数は同じ変数名であっても別の変数である。

List 10.2.2 ソースファイルtest1.c

#include <stdio.h> int recfunc(int n) {     int x;     if (n<=0) return 0;     printf("A n=%d\n",n);     x=recfunc(n-1)+n;     printf("B n=%d x=%d\n",n,x);     return x; } int main() {     int x;     x=recfunc(4); //1から4までの和を求める     printf("ans=%d\n",x);     return 0; }

実行結果

>test1.exe A n=4 A n=3 A n=2 A n=1 B n=1 x=1 B n=2 x=3 B n=3 x=6 B n=4 x=10 ans=10

ところで，再帰関数内のstatic変数は，呼び出し側と呼び出され側で常に同じものとなる。
関数内に隠されたグローバル変数のように振る舞う。
実はstatic変数は関数内に隠されたグローバル変数であるという表現のほうが実体をよく表している。

List 10.2.3 ソースファイルtest2.c

#include <stdio.h> int recfunc(int n) {     static int nest=0;  /*再帰関数内のstatic変数*/     int x,y;     if (n<=0) return 0;     printf("A nest=%d n=%d\n",nest,n);     nest++;     y=recfunc(n-1);     nest--;     x=y+n;     printf("B nest=%d n=%d x=%d y=%d\n",nest,n,x,y);     return x; } int main() {     int x;     x=recfunc(4);     printf("ans=%d\n",x);     return 0; }

実行結果

>test2.exe A nest=0 n=4 A nest=1 n=3 A nest=2 n=2 A nest=3 n=1 B nest=3 n=1 x=1 y=0 B nest=2 n=2 x=3 y=1 B nest=1 n=3 x=6 y=3 B nest=0 n=4 x=10 y=6 ans=10

「List 10.2.3 ソースファイルtest2.c」の動作の様子はつぎのようになる。
　どこのprintfで何が表示されているか，ゆっくり追いかけて理解しなさい。

	３．再帰の例（ハノイの塔）

こま数が４のハノイの塔 大きさの異なる４つのこまがある。（右の図で#1～#4） こまを置くことができるのは3箇所（P0,P1,P2）である。 現在そのうちの1箇所（P0）に４つのこまが積んである。 ゲームの目的は，積んであるこまを，すべて別の場所(ここではP2)に積みかえる事である。 ただし，積み替えの移動においては一度のに１つのこましか動かせない。こまには大小関係があり，大きなこまの上に小さなこまを乗せるようにしか，こまを積むことができない。移動の例はここにある。PCに保存し てから実行してみなさい。

以上のようなルールでP0からP2に塔を移動させる手順を見つけ出すことにする。

1つの関数の作業内容は，次のようになる。

#1～#4をP0からP2に移すには，#1～#3をP0からP1に移し，#4をP0からP2に移し，#1～#3をP1からP2に移せばよい。
（「#1～#3をP0からP1に移す」を別の関数に任せ，「#4をP0からP2に移す」を自分で行い，再び「#1～#3をP1からP2に移す」を別の関数に任せる）

#1～#3をP0からP1に移すには，#1～#2をP0からP2に移し，#3をP0からP1に移し，#1～#2をP2からP1に移せばよい。 （「#1～#2をP0からP2に移す」を別の関数に任せ，「#3をP0からP1に移す」を自分で行い，再び「#1～#2をP2からP1に移す」を別の関数に任せる）
　　　　　　　　　　　　　　　　　　：

「別の関数に任せる」というのは，「別の関数がどのような方法で任せた作業を行っているのかは気にせずにとにかく任せてしまう」という考え方が大事である。

P0上のn個のこまを，P1に移動させるには
（１）別な関数に，P0上のn-1個のこまをP2に退避させるように頼み
（２）自分で，P0上の残りの大きいこまをP1に移動させ
（３）別な関数に，P2上に退避したn-1個のこまをP1に移動させるように頼む
という手順の関数を再帰呼び出しすればよい。

List 10.3.1 ソースファイルhanoi.c

#include <stdio.h> #define NUMBER 4 /*moving the pile(number) from source to destination*/ /*#1から#numberのこまを場所souraceから場所destinationに移動させる関数*/ /*場所を表す番号は0,1,2の3か所*/ void movepile(int number,int source,int destination) {     static int count=0;     int temp;     if (number) { /*無限呼び出しにならない保障(number==0ならなにもしない)*/         /*tempは0,1,2のうちsourceでもdestinationでもない値になる*/         temp=3-source-destination;         /*sourceにあるnumber-1個のこまを場所tempに退避*/         movepile(number-1,source,temp);         printf("count=%4d : Move disk #%d from (P%d) to (P%d)\n",                  ++count,number,source,destination);         /*tempに退避していたnumber-1個のこまをdestinationへ*/         movepile(number-1,temp,destination);     } } int main() {     int number=NUMBER;     int source=0;  /*移動元*/     int destination=2; /*移動先*/     movepile(number,source,destination);     return 0; }

実行結果

>hanoi count=   1 : Move disk #1 from (P0) to (P1) count=   2 : Move disk #2 from (P0) to (P2) count=   3 : Move disk #1 from (P1) to (P2) count=   4 : Move disk #3 from (P0) to (P1) count=   5 : Move disk #1 from (P2) to (P0) count=   6 : Move disk #2 from (P2) to (P1) count=   7 : Move disk #1 from (P0) to (P1) count=   8 : Move disk #4 from (P0) to (P2) count=   9 : Move disk #1 from (P1) to (P2) count=  10 : Move disk #2 from (P1) to (P0) count=  11 : Move disk #1 from (P2) to (P0) count=  12 : Move disk #3 from (P1) to (P2) count=  13 : Move disk #1 from (P0) to (P1) count=  14 : Move disk #2 from (P0) to (P2) count=  15 : Move disk #1 from (P1) to (P2)

チェス盤上をKnight（騎士）が動き回り，すべてのセルを訪問する経路を見つけるゲームである。
ただし，Knight（騎士）の動きは次の通りである。◇は現在位置を表し，○は移動可能なセルを表わす。

○
		○		○
	○				○
			◇
	○				○
		○		○

チェス盤は８×８の大きさであるが，手始めに５×５の盤面について訪問順を見つけることにする。

例えば,左上のセルからスタートして，次の番号順に訪問すれば，全部のセルを訪問したことになる。

全部の行き先を確かめてゆくが，ループだけでは探索を実現することが出来ない。
再帰を使って，あるセルに移動できたらその先を探す，そうでなかったら次の探索に移るというバックトラックの手法を使う。

盤の大きさのint型二次元配列を作り，盤をイメージする。未訪問のセルには０を，既訪問のセルには訪問順を表す自然数を格納してゆく。
盤の端のチェックを考えるとプログラムが大変になるので，周囲に２列余分に配列を作り，-１を埋めておく。
そして，あるセルが０だったらそのセルに動くことが可能であるを判断すればよいことになる。
（周囲には2列の-1が入ったセルには動くことができないという性質を使うことにより，盤からはみ出すかどうかという特別な検査を必要としない。）

-1	-1	-1	-1	-1	-1	-1	-1	-1
-1	-1	-1	-1	-1	-1	-1	-1	-1
-1	-1	１	0	0	0	0	-1	-1
-1	-1	0	0	0	0	0	-1	-1
-1	-1	0	0	0	0	0	-1	-1
-1	-1	0	0	0	0	0	-1	-1
-1	-1	0	0	0	0	0	-1	-1
-1	-1	-1	-1	-1	-1	-1	-1	-1
-1	-1	-1	-1	-1	-1	-1	-1	-1

実行結果を画面でなくファイルに保存する簡単な方法を与える。　GoAndSave.cmd　 をダウンロードして，作成されている実行形式ファイルxxxx.exeをこの　GoAndSave.cmd　 のアイコン上にドラッグ＆ドロップする。　本来画面に表示される内容はテキストファイルxxxx_out.txtに書き込まれる。

課題

（１）List 10.2.1 sum.c を参考にしてｎ階乗を求めるプログラムを再帰を用いて作りなさい。 （p10ex01.c）
次の検証用mainを使いなさい。

int factorial(int n)
{
    この中身を自分で作る
}

int main()
{
    int i;
    int fact;
    for (i=1; i<=12; i++) {
        fact=factorial(i);
        printf("factorial(%d)=%d\n",i,fact);
    }
}

参考
　2の階乗　2!=2×1=2
　3の階乗　3!=3×2×1=6
　4の階乗　4!=4×3×2×1=24
　　　：

（２）エイトクイン（Eight Queens）というゲームがある。８×８のチェス盤に８つのクインを置くゲームである。
ただしクインはお互いに移動が自由でなければならない。すなわち自分の移動可能領域に他のクインがいてはいけない。
表示例にあるように，８つのクインの 置き方をすべて見つけなさい。表示例 （p10ex02.c）

Queen（クイン）の移動可能領域は次のとおり前後左右両斜め方向すべてのセルである。◆はクインの現在位置(3,4)を表し，○は移動可能なセルを表わす。行(row)は横方向の並びであり，列(column)は縦方向の並びを表わす。

作業は第0列から順にクインを置くことにする。下図では●はすでに置かれたクインを表わしている。
現在(0,0)，(2,1)，(4,2)まで置いたところで，第3列に置こうとしているところである。
(3,3)に置けるかどうかをチェックしているところであるが，
水色の矢印方向はまだ何も置かれていないことは明らかなので
赤の矢印方向にすでに置かれたクインが存在するかどうかを確かめればよい。
図ではすでにクインが赤矢印上にあるので，(3,3)には新しいクインを置くことができない。

考え方

mainさん：0列目の作業をお願い 再帰関数Aさん：0列目をお願いされました。 　「(0,0)に置けるかどうかチェックして置けるなら 　　(0,0)にQueenを置いてから 　　（0列目だから置けるのは当たり前） 　　再帰関数Bさんに1列目の作業をお願いする 　　(0,0)のQueenを取り去る」 同じ作業を、(1,0),(2,0)...(7,0)まで行う 再帰関数Bさん：1列目をお願いされました。 　「(0,1)に置けるかどうかチェックして置けるなら 　　(0,1)にQueenを置いてから 　　再帰関数Cさんに2列目の作業をお願いする 　　(0,1)のQueenを取り去る」 同じ作業を、(1,1),(2,1)...(7,1)まで行う 再帰関数Cさん：2列目をお願いされました。 　「(0,2)に置けるかどうかチェックして置けるなら 　　(0,2)にQueenを置いてから 　　再帰関数Dさんに3列目の作業をお願いする 　　(0,2)のQueenを取り去る」 同じ作業を、(1,2),(2,2)...(7,2)まで行う 再帰関数iさん：i列目をお願いされました。 　「(0,i)に置けるかどうかチェックして置けるなら 　　(0,i)にQueenを置いてから 　　再帰関数i+1さんにi+1列目の作業をお願いする 　　(0,i)のQueenを取り去る」 同じ作業を、(1,i),(2,i)...(7,i)まで行う

骨組みの例

char board[8][8]; /*クインを置いてある場所は'Q'，そうでない場所は'o'で表わすものとする。*/ void printBoard(void) {     /* ８×８の盤面を表示 */     /* 実装は自分で考えて */ } /*column列に関する作業*/ void columnwork(int column) {     int row;     int status;     if (column==8) { /*column=8でこの関数が呼び出されたら，解が見つかっているということなので*/         printBoard(); /*発見された解を表示*/         return;     }     for (row=0; row<8; row++) {/*引数で受け取ったcolumnについてrow=0～7まで検査*/         /* ここでrow行column列の位置にクインがおけるかどうかのチェック   　　　*/         /* 置くことが可能ならstatusには1,そうでなければ0が入っているようにする */         /* 実装は自分 で                                                 　　　*/         if (status==1) { /*row行column列の位置にクインが置けるなら*/             /* row行column列の位置にクインを置く                */             /* （board[8][8]中のrow行column列の位置を'Q'にする）*/             /* 実装は自分 で                                    */             columnwork(column+1); /*（column+1）列の作業をする*/             /* row行column列の位置のクインをはずす              */             /* （board[8][8]中のrow行column列の位置を'o'にする）*/             /* 実装は自分 で                                    */         }     } } void initBoard(void) {     /* すべての盤面をクリア，初期状態にする   */     /* （board[8][8]のすべてを'o'にする）     */ } int main() {     initBoard();     columnwork(0);/*最初は第0列から作業を開始*/     return 0; }

次のような考え方もある  （配列を使ってチェックを簡単にする）

/***************************************************************** クイーンを置く際に行のすべてのセルのチェック，２つの斜め列のすべての セルのチェックを行ってもよいが，置く時にある行がまだおけるかどうかの チェック配列にしるしをつけておくことで，チェックを簡素化できる。 　　　列↓   x 0 1 2 3 4 5 6 7 y                   0  o o o o o o o o  1  o o o o o o o o　行  2  o o o o o o o o　←  3  o o o o o o o o  4  o o o o o o o o  5  o o o o o o o o  6  o o o o o o o o  7  o o o o o o o o 置かれたクイーンにより行が占有されているかどうかを示す配列：rowline[8]   x 0 1 2 3 4 5 6 7 y                    配列要素番号  0  o o o o o o o o   0  1  o o o o o o o o   1  2  o o o o o o o o   2  3  o o o o o o o o   3  4  o o o o o o o o   4  5  o o o o o o o o   5  6  o o o o o o o o   6  7  o o o o o o o o   7 置かれたクイーンにより「左下から右上方向の列」が占有されているかどう かを示す配列：rightupline[15] (x,y)　なら　配列要素番号は　x+y     0 1 2 3 4 5 6 7　　　　　↓       0 1 2 3 4 5 6 7 8 91011121314  rightupline[15]  0  o o o o o o o o . . . . . . .  1  o o o o o o o o . . . . . .  2  o o o o o o o o . . . . .  3  o o o o o o o o . . . .  4  o o o o o o o o . . .  5  o o o o o o o o . .  6  o o o o o o o o .  7  o o o o o o o o 置かれたクイーンにより「左上から右下方向の列」が占有されているかどう かを示す配列：rightdownline[15] (x,y)　なら　配列要素番号は　y-x+7     0 1 2 3 4 5 6 7                     0  o o o o o o o o   rightdownline[15]  1  o o o o o o o o 0  2  o o o o o o o o 1  3  o o o o o o o o 2  4  o o o o o o o o 3  5  o o o o o o o o 4  6  o o o o o o o o 5  7  o o o o o o o o 6       . . . . . . . 7         . . . . . . 8 ←配列要素番号           ..  . . . 9             . . . .10               . . .11                 . .12                   .13                    14 *****************************************************************/ char board[8][8];        //置かれている：「Q」，いない「o」 char rowline[8];         //行の占有状態を示す配列 0 or 1 char rightupline[15];    //「左下から右上方向の列」の占有状態を示す配列 0 or 1 char rightdownline[15];  //「左上から右下方向の列」の占有状態を示す配列 0 or 1 void printBoard(void) {     /* ８×８の盤面を表示 */     /* 実装は自分で考えて */ } void columnwork(int column) //列に関する作業 {     int row;     if (column==8) {         printBoard();         return;     }     for (row=0; row<8; row++) {         if (rowline[row]==0 && rightupline[row+column]==0 && rightdownline[row-column+7]==0) {             rowline[row]=1;             rightupline[row+column]=1;             rightdownline[row-column+7]=1;             board[row][column]='Q';             columnwork(column+1);             rowline[row]=0;             rightupline[row+column]=0;             rightdownline[row-column+7]=0;             board[row][column]='o';         }     } } void initBoard(void) {     /*     すべての配列要素を初期化する     board[i][j]はすべて'o';     rowline[i]，rightupline[i]，rightdownline[i]はすべて0;     実装は自分で     */ } int main() {     initBoard();     columnwork(0); }

実行結果を画面でなくファイルに保存する簡単な方法を与える。　GoAndSave.cmd　 をダウンロードして，
（IEなどではマウス右クリックでファイル保存を選ぶ。Windowsの警告が出るが，このファイルは安全なので無視してよい）
作成されている実行形式ファイルxxxx.exeをこの　GoAndSave.cmd　 のアイコンの上にドラッグ＆ドロップする。
（GoAndSave.cmdを起動して，起動した画面にドロップするのではない。）
（実行時にもWindowsの警告が出るが，このファイルは安全なので無視してよい）　
本来画面に表示される内容はテキストファイルxxxx_out.txtに書き込まれる。

（３）騎士巡行につ いて８×８以上の場合（９×９，１０×１０，．．．）について最低3個の経路 を探しなさい。
（発展課題 提出は自由ですが，Ｓ評価をねらう場合には挑戦してください。）
探索時間が爆発的に増えるので，不要な探索は,はやめに発見し，打ち切るような改良が必要になる場合があります。
　　（p10ex03.c）

Pentium4（1.6GHz）ノートパソコンでの実行 例（実行結果，経過時間も表示されています，もっと早いプログラムを開発してください。）
５×５，６×６，7×７，．．．，３０×３０までの盤面で，不要な探索を打ち切りながらそれぞれ3つずつ解を探した例。
　実行例　windows実行ファ イル例
６×６，８×８，．．．，３０×３０までの偶数×偶数のみで，しかも起点に戻る解をそれぞれ3つずつ探した例。
　実行例　windows実行 ファイル例

実は，騎士巡行は，1823年にWarnsdorffが示したルールでバックトラック法を用いると，「不要な探索を打ち切り」
を用いなくとも，３０×３０くらいなら，簡単に巡行経路を求めることができることが知られている。

ワーンスドロフの規則：with Warnsdorf's Heuristic
次のセルに移動しようとして複数の候補セルがあるとき，
その候補セルから次に移動可能なセルを数え，これを候補セルの自由度とする。
自由度が最も少ない候補セル順に次への移動を選ぶ。

しかし，このルールで探索しても，大きな盤面になると，成功率が下がってくることをSquirrel, Douglas， Paul Cull.が1996年に示している。
実際このルールを適応したプログラムを作成した例を示す。
Warnsdorffのルールでの実行ファイル例
5×5から7×7・・・とすべて探索すると残念ながら63×63までは見つけられるが64×64で長時間探索にはいってしまって，
いつ終わるかわからない状況になって探索失敗と判定された。ソースプログラムの最後のところに判定結果がある。
このプログラムをコンパイルする際にスタック領域を増やす必要がある。exeファイルはスタックサイズを変更してコンパイルされている。

Warnsdorffの方法をちょっと工夫して，6×6から7×7・・・，300×300まですべて探索を成功させることができた。
ただし，コンパイル時にスタックエリアを増やすオプションを付けてコンパイルした。
（これをしないとスタックオーバーフローを起こして実行時にエラーになる）　
画面表示に時間がかかるので，実行形式ファイル.exeを　GoAndSave.cmd　 のアイコンの上にドラッグ＆ドロップして実行すると
３０秒くらいで実行結果がファイルとして得られる。
工夫したWarnsdorffのルールでの実行ファイル例

（文章課題）再帰に関するこのページの内容で重要なポイントをまとめてレポートにしなさい。ただし，初めの2行（ファイル名，ID，出席番号，氏名）は，これまでのプログラムと同様な書式で書くこと。　（p10.txt）