第9講 関数の再帰的使用
第4話 関数の再帰的使用によるn次順列生成解説その1

コード再掲
#include<iostream>
using namespace std;
void f(int g);
void h();
int x[15],n;
long cn;
void main(){
   cout<<"何次順列を生成しますか?"<<endl;
   scanf("%d",&n);
   cout<<endl;
   cn=0;
   f(0);
   cout<<n<<"次順列が"<<cn<<"個生成されました。"<<endl;
}
void f(int g){
   int i,j;
   for(
i=1;i<n+1;i++){
     x[g]=
i;
     if(
g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j])goto tobi;
        }
     }
     if(
g+1<n){
        f(
g+1);
     }
     else{
        h();
        cn++;
     }
     tobi:;
   }
}
void h(){
   for(char i=0;i<n;i++)cout<<x[i]<<" ";
   cout<<endl;
}
それでは、
上のコードでなぜn次順列が生成できるのかを解説していきましょう。
魔方陣 数独で学ぶ VBA 入門でもこの話題に触れていますので、
再利用させて頂きます。

n=3の場合で解説していきます。
このコードを理解するためには、
giの役割の違いを理解することです。
void f(int g){
   int i,j;
   for(
i=1;i<n+1;i++){
     x[g]=
i;
     if(
g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j])goto tobi;

gはセル(枠)番号で、左から何番目のセル(枠)かを表す数です。
ただし、1番左のセルは0番目と数えています。
セルを比喩で次元と呼んだり、世界と呼んだりしますと、
gはパラレルワールドの次元番号をして示していることになります。
gが異なれば世界=次元が異なる世界です。
そして、
次元(セル)が違えば、同じiでも次元と次元と次元は別物です。

 

は別次元の世界の住民です。

少しむずしい言い方をしてしましましたが、簡単に言い直すと、
0,1,2はセル(数字や文字を入れる箱)のラベル名(箱の名前)であり、
はそのラベルの貼ってあるセル(数字や文字を入れる箱)の内容です。
は、1,2,3と動き、現象的には0,1,2と似ていますが、
実際には、ビール瓶の例えでは0,1,2はビール瓶のラベルですし、
はビール瓶に入っているビールで、全然違うものです。
セル番号
とセルの中身を明確に区別されてコードを読んでください。

ライラの冒険では、
主人公の女の子はあちらこちらの次元の世界を行ったり来たりしますが、
このプログラムも、いろいろな次元を行ったり来たりします。
今どの次元にいるのか、入れ子式人形例えでは、
外側から何番目の人形のところにいるのかを明瞭・明確に理解していないと、
訳がわからなくなります。
比喩で、

 

と書いていますが、本当はfor文ループ版のときと違い、

 1


 2 3


 3 1 2

と時に応じて様々な姿をしています。
関数は、呼び出されたときだけメモリー上に存在しています。
関数が活動を終えたとき、関数はメモリー上から消滅します。
変数と同じで、関数もメモリー上に存在していて、
メモリー上で生成消滅を繰り返すのです。
まず、mainから、f (
0)で呼び出されて、はじめて世界

 

が生まれます。そして、f (0)からf (1)が呼び出されたとき、2番目の世界

 

が生誕します。そして、f (1)からf (2)が呼び出されて、3番目の世界

 

が発生します。f (2)が任務を遂行し終わると、f (2)は消滅して

 

となります。
同様に、f (1)も処理を終えると、命も終わり

となります。
さらに、f (0)が任務を遂行すると、すべて消えてしまします。
しかし、f (0)・f (1)・f (2)が消滅しても、
生きていたときの活動結果がコンソールに残されるわけです。
つまり、
f (0)・f (1)・f (2)はコンソールに順列をすべて表示させるという任務を終えると、
消滅することが運命づけられているわけです。
順列の生成は、f (0)・f (1)・f (2)の連係プレイによるものですが、
コンソールに結果を表示させるという栄誉ある任務を遂行できるのは
(最後の核ボタンを押す権限をもつのは)、f (2)だけです。
     if(g+1<n){
        f(
g+1);
     }
     else{
        h();
        cn++;
     }

比喩による説明は以上にして、
次話では具体的にトレースしていきます。





第3話へ 第5話へ


a

魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義(基礎から応用まで)
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第1部
eclipse java 入門
java 入門 サイト 基礎から応用まで
VC++ C言語 C++ 入門 初心者 基礎から応用まで
本サイトトップへ