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


解答コード再掲
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
1 2

1個目の順列の作成表示に成功すると、f (2)からf (1)の世界に戻ります。

 0
1 2

となります。f (1)の次のループによって、

 0
1 3

となります。x[1]≠x[0]なので、チェック
      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();
        }
      }
が行われます。
g=1ですから、g + 1 < n  は 1 + 1 < 3
で成り立ち、
        f (
g + 1);
が呼び出され、セル番号
の世界の2回目の来訪となります。

 0
1 3

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

 0
1 3 1

となります。残念ながら、x[2] = x[0] ですから
      h=1;
      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
の1回目のループにおいてh=0と書き換えられ、
     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)の次のループにより、

 0
1 3 2

となります。x[2]≠x[0]、x[2]≠x[1]なので、
      h=1;
      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
において2回ともhは書き換えられず、
     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();
        }
      }
の実行となりますが、
g=2ですから g + 1 < n は  2 + 1 < 3 で成り立ちませんので
        else{
          cn++;
          for(j=0;j<n;j++){
            System.out.print(x[j]);
            System.out.print (" ");
          }
          System.out.println();
        }
が実行され、2個目の順列Javaが表示されることになります。
そして、次のループによって

 0
1 3 3

となりますが、x[2] = x[1]で
      h=1;
      if(
g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
のj=1のとき、h=0と書き換えられ、
     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)のすべての処理が終わり、 f (
2)からf (1)への2度目の帰還となります。

 0
1 3

そして、f (1)も任務が終了して、旅立ち以来はじめてのf (0)への還帰となります。

 0
1

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

 0
2

となりますが、g=0なので、
      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();
        }
      }
の肯定の方が実施され、セル番号
の世界の2回目の歴訪となります。

 0
2

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

 0
2 1

となります。x[1]≠x[0]で、チェック
      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();
        }
      }
の肯定の側が遂行され、セル番号
の世界への3回目の訪問となります。

 0
2 1

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

 0
2 1 1

となります。 x[2] = x[1]
ですので
      h=1;
      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
2回目でh=0に書き換えられ、
     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 2

今度は、 x[2] = x[0]で
      h=1;
      if(
g>0){
        for(j=0;j<g;j++){
          if(x[
g]==x[j]){
            h=0;
            break;
          }
        }
      }
1回目でh=0に書き換えられ、
     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

x[2]≠x[0]、x[2]≠x[1]なので3度目の正直で
      h=1;
      if(
g>0){
        for(j=0;j<g;j++){
          if(x[
g]==x[j]){
            h=0;
            break;
          }
        }
      }
のチェックをクリアして
        else{
          cn++;
          for(j=0;j<n;j++){
            System.out.print(x[j]);
            System.out.print (" ");
          }
          System.out.println();
        }
の命令が行われ、3個目の順列Javaが表示されます。


本日のトレースはここまで。これ以降のトレースは次話で。


第6話へ 第8話へ

戻る

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部