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


解答コード再掲
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();
        }
      }
    }
  }
}

解説
  public static int[] x=new int[20];
  public static int n;
はメンバ変数=クラス変数にしないで、f(g,cn,n,
x)としてプロシージャを呼び出すことも出来ますが、
次元を決定づけているものはgであることを強調するために、
今回はpublic static int[] x=new int[20];とcn、nはメンバ配列=クラス配列とメンバ変数=クラス変数変数にしてあります。このためにf(g)というすっきした呼び出しになっています。
尚、f(g,cn,n,x) のxは配列を引数として引き渡しています。配列も引数として引き渡しが出来ます。
    n=Integer.parseInt(a.readLine());
    cn=0;
1行目で、キーボードから順列の次数を取得しています。
2行目で初期化しています。cnは、順列総数を数えるカウンタ(数えるものという意味です)変数です。
さて、トレースを今からしていきますが、現在どのセル番号の世界にいるのかを常に明確に意識しながら、以下をお読みください。
現在どのセルにいるのかをはっきり掴んでいないと、トレースが理解できなくなります。
現在いるセル(現在アクティブなセル)を

   

で表すことにします。



また、n=3の場合でトレースしていることも念頭においてください。

  f (0);
ではじめて、世界0

 0  
   

に訪れます。
    for(i=1;i<n+1;i++){
      x[g]=i;
最初にiに1が入ります。

 0  
   

      h=1;
      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
g=0ですから、if文は実行されず、h=1は書き換えられず、
     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=0ですから、g + 1 < nは
0 + 1 < nすなわち1 < 3 で成り立ちますので、
        f (
g + 1);
の命令が遂行されます。
g=0ですから、f (g + 1)はf (1)です。したがって、f (0)がf (1)を呼び出しました。
その結果、2番目の世界(セル番号
の世界)

 0  
   

に舞台が変わります。
    for(i=1;i<n+1;i++){
      x[
g]=i;
によって、

 0  
 

となります。g=1ですから、
      h=1;
      if(
g>0){
        for(j=0;j<g;j++){
          if(x[
g]==x[j]){
            h=0;
            break;
          }
        }
      }
のif文が実施され、j=0のとき、x[
g] = x[j] は x[1] = x[0] となり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();
        }
      }
は遂行されません。したがって、次のループによりi=2となり、

 0  
 

今度はj=0のとき、x[1]≠x[0]なので、h=1は書き換えられず、
     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)すなわちf (2)
の命令が遂行されます。すなわち、f (
1)がf (2)を呼び出し、

 0
1 2

3番目の世界(g=2の世界)へと跳躍します。
    for(i=1;i<n+1;i++){
      x[g]=i;
によって、i=1が入り、

 0
1 2 1

となります。
      h=1;
      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
は1回目のループすなわちj=0のとき、x[
g] = x[j] は x[2] = x[0]となり、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();
        }
      }
は遂行されず、次のループによりi=2となり、

 0
1 2 2

となります。
      h=1;
      if(g>0){
        for(j=0;j<g;j++){
          if(x[g]==x[j]){
            h=0;
            break;
          }
        }
      }
今回は、2回目のループすなわちj=1のとき、x[g] = x[j] は x[2] = x[1]となり、
     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 3

となります。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;
          }
        }
      }
のチェックをクリアして、
     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で成り立ちません。
よってf (
2)は、はじめて自分だけに与えられている核ボタンを押す権限
        else{
          cn++;
          for(j=0;j<n;j++){
            System.out.print(x[j]);
            System.out.print (" ");
          }
          System.out.println();
        }
を遂行して、

コマンドプロンプトに1個目の順列入門を表示させることに成功します。

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


第5話へ 第7話へ

戻る

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部