第９講　関数の再帰的使用

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

#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)の消滅は、セル番号２の世界自体の消滅だからです。
初めて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の値は１のままで、
　　　　　　　　　　　　　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)が呼び出され、入れ子式人形が再び３重になります。そして、２回目のf(2)の1巡目のループにより、

となり、
　　　　　　　　　　　　　h=1;
　　　　　　　　　　　　　if(g>0){
　　　　　　　　　　　　　　　for(j=0;j<g;j++){
　　　　　　　　　　　　　　　　　if(a[g]==a[j]){
　　　　　　　　　　　　　　　　　　　h=0;
　　　　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　}
の１巡目において１と１が比較され、内容が同じなので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++;
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　}
はスルーされ、２回目のf(2)の２巡目のループとなり、

　　　　　　　　　　　　　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++;
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　}
が行われます。
ところが、g+1<nは3<3で等しくなく、
　　　　　　　　　　　　　　　if(g+1<n){
　　　　　　　　　　　　　　　　　s=f(g+1,n,a,s);
　　　　　　　　　　　　　　　}
は実行されず、else文の方が実行され、順列の２つめがデータグリッドビューに表示されます。
そして、s++によって順列総数も２をカウントすることになります。
次に、２回目のf(2)の３巡目になり、

　　　　　　　　　　　　　h=1;
　　　　　　　　　　　　　if(g>0){
　　　　　　　　　　　　　　　for(j=0;j<g;j++){
　　　　　　　　　　　　　　　　　if(a[g]==a[j]){
　　　　　　　　　　　　　　　　　　　h=0;
　　　　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　}
の２巡目で３と３が比較され、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++;
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　}
は実施されず、２回目のf(2)の消滅となります。

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

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

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)の２回目の発生となります。

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

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

４回目のf(2)の１巡目によって、

となりますが、
　　　　　　　　　　　　　if(g>0){
　　　　　　　　　　　　　　　for(j=0;j<g;j++){
　　　　　　　　　　　　　　　　　if(a[g]==a[j]){
　　　　　　　　　　　　　　　　　　　h=0;
　　　　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　}
の２巡目の試験をパスせず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++;
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　}
は無視され、４回目のf(2)の２巡目によって

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

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

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

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

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

検査
　　　　　　　　　　　　　if(g>0){
　　　　　　　　　　　　　　　for(j=0;j<g;j++){
　　　　　　　　　　　　　　　　　if(a[g]==a[j]){
　　　　　　　　　　　　　　　　　　　h=0;
　　　　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　}
を突破できず、f(2)は５度目の消滅を体験します。
続いて、f(1)も２度目の消滅を食らいまして、f(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++;
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　}
を実行して、f(1)を呼び出し、f(1)の３回目の生誕となります。

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

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

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

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

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

　　　　　　　　　　　　　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文によって６個目の順列がデータグリッドビューに表示され順列総数も６となります。
以下、６回目の２巡目、３巡目

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

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

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

fは自分の天命を成就して人生劇場から退場したのです。

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




第６話へ　最終講第１話へ

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

数学研究室に戻る