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

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

解答コード再掲
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からｎまでの順列をすべて発生させます。");
　　　　System.out.println("いくつまでの順列かキーボードから入力してください。");
　　　　System.out.print ("ｎ＝");
　　　　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)としてプロシージャを呼び出すことも出来ますが、
次元を決定づけているものはｇであることを強調するために、
今回はpublic static int[] x=new int[20];とｃｎ、ｎはメンバ配列＝クラス配列とメンバ変数＝クラス変数変数にしてあります。このためにｆ（ｇ）というすっきした呼び出しになっています。
尚、f(g,cn,n,x) のxは配列を引数として引き渡しています。配列も引数として引き渡しが出来ます。
　　　　n=Integer.parseInt(a.readLine());
　　　　cn=0;
１行目で、キーボードから順列の次数を取得しています。
２行目で初期化しています。ｃｎは、順列総数を数えるカウンタ（数えるものという意味です）変数です。
さて、トレースを今からしていきますが、現在どのセル番号ｇの世界にいるのかを常に明確に意識しながら、以下をお読みください。
現在どのセルにいるのかをはっきり掴んでいないと、トレースが理解できなくなります。
現在いるセル（現在アクティブなセル）を

で表すことにします。

また、ｎ＝３の場合でトレースしていることも念頭においてください。
　　f (0);
ではじめて、世界０

０	１	２
ｉ

に訪れます。
　　　　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文は実行されず、ｈ＝１は書き換えられず、
　　　　　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 < nは0 + 1 < nすなわち1 < 3 で成り立ちますので、
　　　　　　　　f (g + 1);
の命令が遂行されます。ｇ＝０ですから、f (g + 1)はf (1)です。したがって、f (0)がf (1)を呼び出しました。
その結果、２番目の世界（セル番号１の世界）

０	１	２
１

に舞台が変わります。
　　　　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文が実施され、ｊ＝０のとき、x[g] = x[j] は x[1] = x[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();
　　　　　　　　}
　　　　　　}
は遂行されません。したがって、次のループによりｉ＝２となり、

０	１	２
１	２

今度はｊ＝０のとき、x[1]≠x[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();
　　　　　　　　}
　　　　　　}
が実行されます。ｇ＝１ですから、g + 1 < n は　1 + 1 < 3で真ですから、
　　　　　　　　f (g + 1)すなわちf (2)
の命令が遂行されます。すなわち、f (1)がf (2)を呼び出し、

０	１	２
1	2	ｉ

３番目の世界（ｇ＝２の世界）へと跳躍します。
　　　　for(i=1;i<n+1;i++){
　　　　　　x[g]=i;
によって、ｉ＝１が入り、

０	１	２
1	2	1

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

０	１	２
1	2	2

となります。
　　　　　　h=1;
　　　　　　if(g>0){
　　　　　　　　for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j]){
　　　　　　　　　　　　h=0;
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　}
　　　　　　}
今回は、2回目のループすなわちｊ＝１のとき、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();
　　　　　　　　}
　　　　　　}
は実施にいたらず、次のループにより

０	１	２
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 + 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個目の順列を表示させることに成功します。

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