第10講 関数の再帰的呼び出し=関数の自己再帰の学習
第8話 関数の再帰的呼び出しによる汎用的順列作成プログラム解説その4


解答コード再掲
public class A{
  public static int[] x=new int[20];
  public static int n;
  public static int cn;
  public static void main(String args[]) throws IOException{
    BufferedReader a = new BufferedReader(new InputStreamReader(System.in));
    System.out.println("1からnまでの順列をすべて発生させます。");
    System.out.println("いくつまでの順列かキーボードから入力してください。");
    System.out.print ("n=");
    n=Integer.parseInt(a.readLine());
    cn=0;
    f(0);
    System.out.print ("順列総数=");
    System.out.print (cn);
  }
  public static void f(int g){
    int i,j,h;
    for(i=1;i<n+1;i++){
      x[g]=i;
      h=1;
      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
      if(h==1){
        if(g+1<n){
          f(g+1);
        }
        else{
          cn++;
          for(j=0;j<n;j++){
            System.out.print(x[j]);
            System.out.print (" ");
          }
          System.out.println();
        }
      }
    }
  }
}
 0
2 1 3

これでf (2)の3回目の歴訪が終わり、f (1)へと戻ります。

 0
2 1

そして、次のループにより

 0
2 2

となりますが、これは
      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
によってチェックされてしまい、
      if(h==1){
        if(g+1<n){
          f(
g+1);
        }
        else{
          cn++;
          for(j=0;j<n;j++){
            System.out.print(x[j]);
            System.out.print (" ");
          }
          System.out.println();
        }
      }
無視されますから、次のループにより

 0
2 3

今回は
      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
の試験に合格して       
      if(h==1){
        if(g+1<n){
          f(
g+1);
        }
        else{
          cn++;
          for(j=0;j<n;j++){
            System.out.print(x[j]);
            System.out.print (" ");
          }
          System.out.println();
        }
      }

命令が実施され、f (2)への4回目の跳躍となります。

 0
2 3

    for(i=1;i<n+1;i++){
      x[g]=i;
によって

 0
2 3 1

3つともセルの内容が違いますので、
試験

      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
はあっさりクリアして
      if(h==1){
        if(g+1<n){
          f(
g+1);
        }
        else{
          cn++;
          for(j=0;j<n;j++){
            System.out.print(x[j]);
            System.out.print (" ");
          }
          System.out.println();
        }
      }

の否定側の
        else{
          cn++;
          for(j=0;j<n;j++){
            System.out.print(x[j]);
            System.out.print (" ");
          }
          System.out.println();
        }
の命令が遂行され、4個目の順列入門をコマンドプロンプトにはき出します。
次のループにより、

 0
2 3 2

となりますが、これは1番目のセルと3番目のセルが同じなので、検査
      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
に抵触して、

 0
2 3 3

となります。今度は、2番目のセルと3番目のセルの内容が同じなので、やはり
      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }

の試験をクリアできません。
これで、f (
2)の4回目の歴訪が終わり、f (1)へと帰還します。

 0
2 3

そして、セル番号1の世界の任務が終了し、f (0)への2度目の帰省となります。

 0
2

次のループにより

 0
3

となり、g=0なので試験
      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
スルーされ、
      if(h==1){
        if(g+1<n){
          f(g+1);
        }
        else{
          cn++;
          for(j=0;j<n;j++){
            System.out.print(x[j]);
            System.out.print (" ");
          }
          System.out.println();
        }
      }
の肯定側
      if(h==1){
        if(g+1<n){
          f(g+1);
が実行されf (1)の3度目の来歴となります。

 0
3 i

      if(g>0){
        for(j=0;j<g;j++){

 0
3 1

これは、2つのセルに内容が違いますので、
      if(h==1){
        if(
g+1<n){
          f(g+1);
        }
        else{
          cn++;
          for(j=0;j<n;j++){
            System.out.print(x[j]);
            System.out.print (" ");
          }
          System.out.println();
        }
      }
の肯定部分が遂行され、f (2)の5度目の訪れとなります。

 0
3 1 i

for文によって

 0
3 1 1



 0
3 1 2

と変化していって、はじめて3つのセルの内容がすべて異なり、
      if(h==1){
        if(g+1<n){
          f(g+1);
        }
        else{
          cn++;
          for(j=0;j<n;j++){
            System.out.print(x[j]);
            System.out.print (" ");
          }
          System.out.println();
        }
      }
の否定部分の命令が遂行され5個目の順列Javaがコマンドプロンプトに出力されます。
以下、

 0
3 1 3

セル番号の世界からセル番号1の世界に戻ります。

 0
3 2



 0
3 2 1

と変化していき、6個目の順列初心者がコマンドプロンプトに打ち出されます。

 0
3 2 2



 0
3 2 3



 0
3 2



 0
3 3



 0
3


セル番号の世界のループが終了して、
f (0)を呼び出されてからはじめてmainに戻り、
最後の命令
    System.out.print ("順列総数=");
    System.out.print (cn);
を遂行して、自分の任務をすべて完遂し終焉を迎えます。
プログラムは、消滅しましたが、コマンドプロンプトには結果基礎
が燦然と輝いています。

最後の方、叙述を簡単にしましたが、簡略にした部分を皆さんが補ってください。
詳しい記述を延々と繰り返したのでは、逆に読む気力が失せると考え、簡単にしました。

n=3を選んだ理由はお分かりですね。n=2ではトレースとして簡単すぎます。
しかし、n=4では、私も書く気になれませんし、読む皆さんもウンザリですよね。

みなさん、n=4のトレースは大変ですが、頭の中でやってみてください。
コンピュータの動きを追うことはとても大切なことです。

では、皆さんわかりやすさを優先して、  
  public static int[] x=new int[20];
  public static int n;
  public static int cn;
をグローバル(正確にはクラスメンバ変数)として引数1つの関数public static void f(int g)としましたが、
グローバル配列とグローバル変数をやめて、関数もpublic static void f(int g,int n,int cn,int x[]){と引数を4つにするプログラムを考えてください。
まだ説明していませんが、配列も引数にして、関数に渡すことができます。
引数にするときは、public static void f(int g,int n,int cn,
int x[])のようにするのです。



第7話へ 第9話へ

戻る

VB講義へ
VB講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義(基礎から応用まで)
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第1部
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第2部
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第3部
初心者のための Java 入門 サイト 基礎から応用まで第1部
初心者のための Java 入門 サイト 基礎から応用まで第2部
初心者のための Java 入門 サイト 基礎から応用まで第3部