第40回 プログラミングについて『自分で自分をこき使う話』

『自分で自分をこき使う話』

 
　自分の電話番号に電話をすると話中になっている。自分とは電話で話ができない....
一人暮らしのときに試してみたが、もっと寂しくなってしまった。もしかすると、自分と話ができるとすごく空しいかも知れない。

　こんな経験は私だけなのでしょうか。もし自分がもう一人いたら、そいつに仕事をさせておいて自分は面白おかしく遊んで暮らそう。などとふと頭によぎることがありますが、そんなことはあるはずもなく無駄に妄想に時間を費やすだけです。

　しかしコンピュータの世界では妄想でもなんでもありません。ごく当たり前のことなのです。これまでにもときどき関数が自分自身をこきつかう例を紹介したことはありますが、今回はもう少し腰を入れて考えてみましょう。

　関数が自分自身をこき使うというのは関数の再帰呼び出しのことです。高級言語での関数の再帰呼び出しはＣ言語で始まったものではなく、もっと古い言語であるＡＬＧＯＬあたりがその根源だったかと記憶しています。歴史的には古い機能なのですが、これを許さない言語も当然存在します。

　ＦＯＲＴＲＡＮ７７ではこれはできません。以前Ｃ言語かＰＡＳＣＡＬを使ってプログラムを書いている人に、ＦＯＲＴＲＡＮは自分自身を呼び出すことができないからダサイと言われたことがありました。その当時の私は関数が自分自身を呼び出すなどというだいそれたことは考えてみたこともありませんでしたので大変なショックでした。そこで色々とＦＯＲＴＲＡＮで試してみたものです。

　SUBROUTINE ABC
　　CALL ABC
　END

　と書いてみると、当然のことですがコンパイラに叱られます。次に自分が直接自分を呼び出しているから約束違反なので、

　SUBROUTINE ABC
　　CALL DEF
　END

　SUBROUTINE DEF
　　CALL ABC
　END

　と他の関数に自分を呼び出させてみました。これはコンパイラには叱られません（実行すると無限に呼び出して、スタックがオーバーフローしてしまいます）。ということは、

　CALL ABC(0)
　END

　SUBROUTINE ABC(I)
　　IF(I.GT.10)RETURN

　　WRITE(6,'(I5)')I

　　CALL DEF(I+1)
　END

　SUBROUTINE DEF(I)
　　CALL ABC(I)
　END

　とするとうまく動くはずです。実験してみると確かに望みどおりに、

　　　0
　　　1
　　　2
　　　3
　　　4
　　　5
　　　6
　　　7
　　　8
　　　9
　　 10

となり正常に動作します。では、

　CALL ABC(0)
　END

　SUBROUTINE ABC(I)
　　J=I+1　　　　　　　　　　　　 - (1)
　　IF(I.GT.10)RETURN

　　WRITE(6,'(I5,I5)')I,J

　　CALL DEF(J)　　　　　　　　　 - (2)
　END

　SUBROUTINE DEF(I)
　　CALL ABC(I)
　　RETURN
　　END

　これを実行してみると、

　　　0　　1
　　　1　　2
　　　2　　3
　　　3　　4
　　　4　　5
　　　5　　6
　　　6　　7
　　　7　　8
　　　8　　9
　　　9　 10
　　 10　 11

となるはずが、

　　　0　　1
　　　2　　2
　　　3　　3
　　　4　　4
　　　5　　5
　　　6　　6
　　　7　　7
　　　8　　8
　　　9　　9
　　 10　 10

となってしまうのです。これがＦＯＲＴＲＡＮ７７では関数が自分自身を呼び出せないことになっている最大の理由なのです。ＦＯＲＴＲＡＮは基本的に変数は静的にプログラムの実行中には常に存在しています。また関数の引数はすべてアドレス渡しですので、最初にサブルーチン ABC が呼び出されたときの J と２番目に呼び出されたときの Jも同じアドレスです。また最初に呼び出された ABC が DEF を使って自分自身を呼び出すために引数としてJ を渡すと（J のアドレスが渡されます)、呼び出されたABCが受け取った引数 I のアドレスは実は自分自身の J のアドレスになっている訳です。ということは引数 I のアドレスのところの値は 1 ですので、それに１を加えて J に代入すると、I も J もともに 2 になってしまうのです。
　このような不都合があることからＦＯＲＴＲＡＮは自分自身は呼び出せないことになっているのです。しかしながらＦＯＲＴＲＡＮは時代とともに進化し、ＦＯＲＴＲＡＮ９０では、自動変数も自分自身を呼び出すこともできるようになりました。書き方は簡単で、次のようにサブルーチン ABCにRECURSIVE を指定し、ABC は自分自身を呼び出すものだとコンパイラに教えると、コンパイラはこのサブルーチンの中の変数は自動変数として扱ってくれるので希望どおりに動作します。

　CALL ABC(0)
　END

　RECURSIVE SUBROUTINE ABC(I)
　　J=I+1
　　IF(I.GT.10)RETURN

　　WRITE(6,'(I5,I5)')I,J

　　CALL ABC(J)
　END

　ＦＯＲＴＲＡＮ９０では静的な変数で、再帰呼び出しはできないということが基本ですのでこのように色々とコンパイラに教えることになっています。AUTOMATIC を指定して変数を定義すれば自動変数になります。

　これに対しＣ言語は自動変数で再帰呼び出しは基本ですので、特別に何も指定する必要はありません。次に家系図を作るプログラムを考えてみましょう。

　助三郎　 は 権ノ助 の子供である。
　格ノ心　 は 権ノ助 の子供である。
　くま吉　 は 里緒菜 の子供である。
　八平　　 は 助三郎 の子供である。
　おしん　 は 助三郎 の子供である。
　権の兵衛 は 里緒菜 の子供である。
　屋七　　 は 八平　 の子供である。
　　　　　 ：
　　　　　 ：

　といった親子関係が分かっているとします。これから家系図を作ってみましょう。
分かりやすくするために、親子関係のデータはプログラムに組み込みとします。

　#include <stdio.h>

　struct person_strct{
　　char　 *self_name;　　　　　　　/* 本人の名前 */
　　char *parent_name;　　　　　　　/* 親　の名前 */
　　struct person_strct　*parent;　 /* 親　へのポインタ */
　　struct person_strct *brother;　 /* 兄弟へのポインタ */
　　struct person_strct　 *child;　 /* 子供へのポインタ */
　};

　main()
　{
　　struct person_strct person[]={
　　　　{ "助三郎"　, "権ノ助" ,NULL,NULL,NULL },
　　　　{ "格ノ心"　, "権ノ助" ,NULL,NULL,NULL },
　　　　{ "くま吉"　, "里緒菜" ,NULL,NULL,NULL },
　　　　{ "八平"　　, "助三郎" ,NULL,NULL,NULL },
　　　　{ "おしん"　, "助三郎" ,NULL,NULL,NULL },
　　　　{ "権の兵衛", "里緒菜" ,NULL,NULL,NULL },
　　　　{ "屋七"　　, "八平"　 ,NULL,NULL,NULL },
　　　　{ "光圀"　　, "格ノ心" ,NULL,NULL,NULL },
　　　　{ "イチロー", "里緒菜" ,NULL,NULL,NULL },
　　　　{ "聖子"　　, "与三郎" ,NULL,NULL,NULL },
　　　　{ "たこ八"　, "格ノ心" ,NULL,NULL,NULL },
　　　　{ "与三郎"　, "里緒菜" ,NULL,NULL,NULL },
　　　　{ "里緒菜"　, "光圀"　 ,NULL,NULL,NULL },
　　　　{ "真之"　　, "里緒菜" ,NULL,NULL,NULL },
　　　　{ NULL　　　, NULL　　 ,NULL,NULL,NULL }};
　}

　まず上のように構造体を作り初期データを定義します。最初に自分の子供は誰なのかを計算します。

　　int i,j,k;

　　for(i=0;person[i].self_name;i++){
　　　for(j=0;person[j].self_name;j++){
　　　　if(i==j)continue;　/* 自分自身は対象外 */

　　　　　　　　　　　　　 /* 自分以外の人が自分の親であるか否かを調べます */
　　　　if(strcmp(person[j].self_name,person[i].parent_name)==0){
　　　　　person[i].brother=person[j].child;　/* 親に子供がいるときにはそれを　　　　　　　　　　　　　　　　　　　　　　 自分の兄弟とする */

　　　　　person[j].child　=person+i;　　　　 /* 自分を親の子供とする */
　　　　　break;
　　　　}
　　　}
　　}

　これだけの操作である人の子孫とその兄弟が設定されます。次にご先祖様を知るためにそれぞれの人の親を計算します。

　for(i=0;person[i].self_name;i++){
　　if(person[i].parent==NULL
　　&& person[i].child !=NULL){　/* 親が設定されていなくて、子供がいる人について計算します */
　　　set_parent(NULL,person+i);
　　}
　}

　ここで set_parent の第１引数は親のポインタで、第２引数は設定する人です。この
set_parent は、

　set_parent(parent,person)
　struct person_strct *parent;
　struct person_strct *person;
　{
　　if(person){
　　　person->parent=parent;　　　　　　　/* 自分の親は当然親にする */

　　　set_parent(parent,person->brother); /* 自分の兄弟には自分と同じ親を
　　　　　　　　　　　　　　　　　　　　　　 設定させる */

　　　set_parent(person,person->child);　 /* 自分の子供には自分を親に
　　　　　　　　　　　　　　　　　　　　　　 設定させる */
　　}
　}

　この関数は再帰呼び出しを行なうものです。上のリストを見れば理屈は簡単に分かると思いますが、再帰呼び出しを行なうときにはあまり難しく考えると頭の中が無限ループになってしまいますので深刻には考えないようにしましょう。
　この関数は自分の親は引数で教えられた親で、自分の兄弟も同じ親、自分の子供は自分が親という簡単な理屈を記述しています。この関係の設定が自分のすべての子孫に対して行われることになります。

　最後に家系図を表示します。表示は簡単にするために一族だけのものとし名前は１０桁とします。

　　j=1;
　　for(i=0;person[i].self_name;i++){
　　　if(person[i].parent==NULL){　/* 親がいない人の子孫を表示させます */
　　　　if(j){
　　　　　　　　　　　　　　　　　 /* 最初の一回はご先祖様の名前を表示します */
　　　　　printf("%-10s",person[i].parent_name);
　　　　　j=0;
　　　　}
　　　　else{
　　　　　　　　　　　　　　　　　 /* 親のいない人の２人目以降の人については
　　　　　　　　　　　　　　　　　　　ご先祖様の名前ではなく、段下げのみを行
　　　　　　　　　　　　　　　　　　　います */
　　　　　for(k=0;k<10;k++)printf(" ");
　　　　}

　　　　display(person+i,10);　　　/* この関数で子孫の系図を表示します */
　　　}
　　}

　この display は次に示します。この関数も再帰呼び出しを行ないます。

　display(person,depth)
　struct person_strct *person;
　int depth;
　{
　　int i;

　　printf("%-10s",person->self_name);　/* 自分の名前を表示します */

　　　　　　　　　　　　　　　　　　　　/* 子供がいるときには
　　　　　　　　　　　　　　　　　　　　　 子供の名前を書きます */
　　if(person->child)display(person->child,depth+10);
　　else　　　　　　 printf("\n");　　　/* 子供がいないときには改行 */

　　if(person->brother){　　　　　　　　/* 兄弟がいるときには段下げをしてから
　　　　　　　　　　　　　　　　　　　　　 兄弟の名前を表示します */
　　　for(i=0;i<depth;i++)printf(" ");
　　　display(person->brother,depth);
　　}
　}

　実にこれだけです。この関数もおおよそ理屈どおりに記述しています。実行結果は次のようになります。

権ノ助　　助三郎　　おしん　　
　　　　　　　　　　八平　　　屋七　　　
　　　　　格ノ心　　たこ八　　
　　　　　　　　　　光圀　　　里緒菜　　真之　　　
　　　　　　　　　　　　　　　　　　　　与三郎　　聖子　　　
　　　　　　　　　　　　　　　　　　　　イチロー　
　　　　　　　　　　　　　　　　　　　　権の兵衛　
　　　　　　　　　　　　　　　　　　　　くま吉　　

　この図を見れば権ノ助がご先祖様で、その子供に助三郎と格ノ心。助三郎はおしんと八平の２人の子供をもうけ、おしんは屋七を産んでいます。格ノ心はたこ八と光圀の２人の子供を作り、光圀は里緒菜を作っています。里緒菜はばんばん産みまくって５人の子宝に恵まれ、真之は浮気をして離婚し、与三郎は歌舞伎役者になった。イチローは野球選手になり、権の兵衛のその後は知られておらず、くま吉は家出をして長屋に住み着いて楽しく暮らした。与三郎には一粒種の聖子が生まれたが聖子は毛唐が大好きで、亭主とは別れてしまった。

　これは余計でした....

　再帰呼び出しを行なっているとき、入れ子が深くなるとスタックサイズを大きく使えないシステムではスタックを使い切ってしまうことがありますので注意が必要です。こういうときには、再帰呼び出しを行なう関数のはなるべく小さく記述してできる限りスタックを使用する量を減らすようにしなければなりません。そのためには必要以外のことは別の関数にしたり、部分的に変数を生成させるようにするなど（ブロック内で変数を生成させ、ブロック終了と同時に消滅させる）など瞬間的に使用するスタックの量を減らす工夫が必要です。

　再帰呼び出しを行なえないくらいにスタックサイズが小さいときには、再帰呼び出しをあきらめて、ループに置き換えるようにしなければなりません。
　例えば上の例の set_parent は、

　set_parent(parent,person)
　struct person_strct *parent;
　struct person_strct *person;
　{
　　struct stack_strct{
　　　struct person_strct *parent;
　　　struct person_strct *person;
　　　struct stack_strct　*next;
　　};
　　struct stack_strct *stack=NULL;
　　struct stack_strct *tmp;

　　while(person){
　　　person->parent=parent;

　　　if(person->child){
　　　　if(person->brother){
　　　　　tmp=(struct stack_strct *)malloc(sizeof(struct stack_strct));
　　　　　tmp->parent=parent;
　　　　　tmp->person=person->brother;
　　　　　tmp->next　=stack;

　　　　　stack=tmp;
　　　　}

　　　　parent=person;
　　　　person=person->child;
　　　}
　　　else if(person->brother){
　　　　if(person->brother){
　　　　　tmp=(struct stack_strct *)malloc(sizeof(struct stack_strct));
　　　　　tmp->parent=parent;
　　　　　tmp->person=person->brother;
　　　　　tmp->next　=stack;

　　　　　stack=tmp;
　　　　}

　　　　person=person->brother;
　　　}
　　　else if(stack){
　　　　parent=stack->parent;
　　　　person=stack->person;

　　　　tmp=stack;
　　　　stack=stack->next;
　　　　free(tmp);
　　　}
　　　else{
　　　　break;
　　　}
　　}
　}

　とすれば同じ結果になります。この例では再帰呼び出しを行なう代わりに、子供や兄弟の設定を行なうときに、次の兄弟の情報を変数　stack に記憶しておくようにしてループを生成しています。このように再帰呼び出しをループに置き換えることはかなりしんどい作業になりますが、最後の手段として腹をくくって記述しなければなりません。

　それではまた次回。