第9講 関数の再帰的使用

第7話 関数の再帰的使用による順列の作成の解説

#pragma once
#include<stdlib.h>
namespace 順列作成 {
      ・
      ・
      ・
#pragma endregion
   private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
           int n;
           int *a;
           long s=0;

           dataGridView1->Rows->Clear();

           n=int::Parse(textBox1->Text);
           a=(int* )malloc(4*n);
           s=f(0,n,a,s);
           dataGridView1->Rows->Add();
           dataGridView1[12,s+1]->Value =s.ToString();
        }
        long f(int g,int n,int* a,long s){
           int i,j,h;
           for(i=1;i<n+1;i++){
             a[g]=i;
             h=1;
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
             if(h==1){
               if(g+1<n){
                 s=f(g+1,n,a,s);
               }
               else{
                 dataGridView1->Rows->Add();
                 for(j=0;j<n;j++){
                   dataGridView1[j,s]->Value =a[j];
                 }
                 s++;
               }
             }
           }
           return s;
         }
};
}

セルの内容 
セル番号 

の続きをトレースしましょう。の世界のループの最後ですから、入れ子式人形の一番内側の人形f(2)は終了となります。
long f(int g,int n,int* a,long s)の宣言を見れば判るとおり、fはstatic関数ではありませんので、普通の関数です。
言い換えると動的関数です。前に説明したとおり、動的関数は生成消滅を繰り返します。
呼び出されたときだけ、メモリ上に存在し、終了するとメモリから消えてしまいます。
ですからf(2)は終了と同時に消滅します。
入れ子式人形の比喩も終わりとなります。
なぜなら、入れ子式人形の各人形は消滅はしません。
ですが、自己再帰型の場合終了と同時にもっとも内側の人形が消滅するのです。つまり、

セルの内容 
セル番号 

となります。本当はもっと正確に表示すると

セルの内容 
セル番号 

です。関数f(2)の消滅は、セル番号2の世界自体の消滅だからです。
初めてbutton1_Clickからf(0)が呼び出されてきたときも正確には、

セルの内容 
セル番号 

ではなく、

セルの内容 
セル番号 

です。f(0)、f(1)、f(2)は呼び出されたときだけ生まれます。
入れ子式人形の比喩で説明してきましたが、
初めてbutton1_Clickからf(0)が呼び出されてきたときには、人形はf(0)しか存在しません。
つまり、この段階では入れ子式人形になっていないのです。
f(0)がf(1)を呼び出したとき、

セルの内容 
セル番号 

初めて入れ子式人形になるのです。
つまり、fがfを呼び出したとき初めて入れ子式人形になるのです。
自分が自分を呼び出したときに、呼び出した自分が外側の人形になり、
呼び出された自分が内側の人形になるのです。
ですから、自己再帰型の関数を比喩的に表す入れ子式人形は、
発生したり、消滅したりを繰り返す奇妙な人形です。

話を戻しましょう。

セルの内容 
セル番号 

セル番号の世界に戻るとfor(i=1;i<n+1;i++)によって、セル番号の世界最後のループ

セルの内容 
セル番号 

となります。
             h=1;
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
によって、が比較されますが内容が一致しないので、hの値は1のままで、
             if(h==1){
               if(g+1<n){
                 s=f(g+1,n,a,s);
               }
               else{
                 dataGridView1->Rows->Add();
                 for(j=0;j<n;j++){
                   dataGridView1[j,s]->Value =a[j];
                 }
                 s++;
               }
             }
が実行されf(2)が呼び出され、入れ子式人形が再び3重になります。そして、2回目のf(2)の1巡目のループにより、

セルの内容 
セル番号 

となり、
             h=1;
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
の1巡目においてが比較され、内容が同じなのでh=0となります。
したがって、
             if(h==1){
               if(g+1<n){
                 s=f(g+1,n,a,s);
               }
               else{
                 dataGridView1->Rows->Add();
                 for(j=0;j<n;j++){
                   dataGridView1[j,s]->Value =a[j];
                 }
                 s++;
               }
             }
はスルーされ、2回目のf(2)の2巡目のループとなり、

セルの内容 
セル番号 

             h=1;
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
の1巡目と2巡目においてそれぞれ、が比較されますがいずれも内容が違いますので、
             if(h==1){
               if(g+1<n){
                 s=f(g+1,n,a,s);
               }
               else{
                 dataGridView1->Rows->Add();
                 for(j=0;j<n;j++){
                   dataGridView1[j,s]->Value =a[j];
                 }
                 s++;
               }
             }
が行われます。
ところが、g+1<nは3<3で等しくなく、
               if(g+1<n){
                 s=f(g+1,n,a,s);
               }
は実行されず、else文の方が実行され、順列の2つめがデータグリッドビューに表示されます。
そして、s++によって順列総数も2をカウントすることになります。
次に、2回目のf(2)の3巡目になり、

セルの内容 
セル番号 

             h=1;
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
の2巡目で3と3が比較され、h=0となり、
             if(h==1){
               if(g+1<n){
                 s=f(g+1,n,a,s);
               }
               else{
                 dataGridView1->Rows->Add();
                 for(j=0;j<n;j++){
                   dataGridView1[j,s]->Value =a[j];
                 }
                 s++;
               }
             }
は実施されず、2回目のf(2)の消滅となります。

セルの内容 
セル番号 

そして、f(1)のループも終わりf(1)が消滅します。

セルの内容 
セル番号 

そして、f(0)の2巡目が行われ

セルの内容 
セル番号 

g=0から
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
はスルーされ、
             if(h==1){
               if(g+1<n){
                 s=f(g+1,n,a,s);
               }
               else{
                 dataGridView1->Rows->Add();
                 for(j=0;j<n;j++){
                   dataGridView1[j,s]->Value =a[j];
                 }
                 s++;
               }
             }
の命令が実施され、f(1)の2回目の発生となります。

セルの内容 
セル番号 

2回目のf(1)の1巡目によって

セルの内容 
セル番号 

となりますが、は一致しないので
すぐにf(2)がよびだされ、f(2)の4回目の発生となります。

セルの内容 
セル番号 

4回目のf(2)の1巡目によって、

セルの内容 
セル番号 

となりますが、
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
の2巡目の試験をパスせずh=0となり、
             if(h==1){
               if(g+1<n){
                 s=f(g+1,n,a,s);
               }
               else{
                 dataGridView1->Rows->Add();
                 for(j=0;j<n;j++){
                   dataGridView1[j,s]->Value =a[j];
                 }
                 s++;
               }
             }
は無視され、4回目のf(2)の2巡目によって

セルの内容 
セル番号 

となります。
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
の1巡目の検査に抵触して、4回目のf(2)の3巡目

セルの内容 
セル番号 

になりますが、
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
の1巡目と2巡目を簡単にクリアして、
             if(h==1){
               if(g+1<n){
                 s=f(g+1,n,a,s);
               }
               else{
                 dataGridView1->Rows->Add();
                 for(j=0;j<n;j++){
                   dataGridView1[j,s]->Value =a[j];
                 }
                 s++;
               }
             }
が舞台に登場しますが、3<3から前半のif(g+1<n)は活躍の場がなく、
else文に主役の座を譲ります。
こうして、データグリッドビューに3個目の順列が表示されカウンタも3となります。
これで4回目のf(2)は4度目の消滅を迎え、

セルの内容 
セル番号 

2回目のf(1)の2巡目となりますが、
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
の検査をクリアできずあっさり2回目のf(1)の3巡目となり、

セルの内容 
セル番号 

今度は
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
をパスして、f(2)の5回目の発生となります。
その1巡目は

セルの内容 
セル番号 

             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
をクリアして、4個目の順列がデータグリッドビューに表示されカウンタも4を数えます。
5回目のf(2)の2巡目と3巡目はそれぞれ、

セルの内容 
セル番号 
セルの内容 
セル番号 

検査
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
を突破できず、f(2)は5度目の消滅を体験します。
続いて、f(1)も2度目の消滅を食らいまして、f(0)の3巡目は、

セルの内容 
セル番号 

すぐに
             if(h==1){
               if(g+1<n){
                 s=f(g+1,n,a,s);
               }
               else{
                 dataGridView1->Rows->Add();
                 for(j=0;j<n;j++){
                   dataGridView1[j,s]->Value =a[j];
                 }
                 s++;
               }
             }
を実行して、f(1)を呼び出し、f(1)の3回目の生誕となります。

セルの内容 
セル番号 

そして、
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
をクリアして、f(2)の6回目の誕生を迎えます。
その1巡目

セルの内容 
セル番号 


             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
をクリアせず、6回目のf(2)の2巡目となり、

セルの内容 
セル番号 

これは
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
のテストをパスして、5個の目の順列がデータグリッドビューに表示されsも5となります。
3巡目

セルの内容 
セル番号 

検査
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
に抵触して、f(2)は5回目の消滅を体験することになります。
3回目のf(1)の2巡目

セルの内容 
セル番号 

検査
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
に合格して、f(2)が呼び出され、f(2)の6回目の生成となります。
6回目のf(2)の1巡目

セルの内容 
セル番号 

             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
の検査を通り抜け、
             if(h==1){
               if(g+1<n){
                 s=f(g+1,n,a,s);
               }
               else{
                 dataGridView1->Rows->Add();
                 for(j=0;j<n;j++){
                   dataGridView1[j,s]->Value =a[j];
                 }
                 s++;
               }
             }
のelse文によって6個目の順列がデータグリッドビューに表示され順列総数も6となります。
以下、6回目の2巡目、3巡目

セルの内容 
セル番号 
セルの内容 
セル番号 

いずれも
             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
に阻止され、f(2)の6回目の消滅と相成ります。
3回目のf(1)の3巡目

セルの内容 
セル番号 

             if(g>0){
               for(j=0;j<g;j++){
                 if(a[g]==a[j]){
                   h=0;
                   break;
                 }
               }
             }
の阻まれ、f(1)は3度目の消滅を迎えます。
そして、

セルの内容 
セル番号 

f(0)も天寿を全うして、入れ子式人形のすべてが消え去ります。
自分が消え去った代わりに、データグリッドビューには6個の順列と総数6が燦然と輝いています。
入門
fは自分の天命を成就して人生劇場から退場したのです。

以上で、関数の再帰的使用による順列の作成の解説を終了とします。
いよいよ最終講卒業研究と卒業試験です。





第6話へ 最終講第1話へ


025


vc++講義へ
vb講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座へ



数学研究室に戻る