第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();
　　　　　　　　}
　　　　　　}
　　　　}
　　}
}

０	１	２
2	1	3

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

０	１	２
2	1

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

０	１	２
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();
　　　　　　　　}
　　　　　　}
無視されますから、次のループにより

０	１	２
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)への４回目の跳躍となります。

０	１	２
2	3	ｉ

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

０	１	２
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個目の順列をコマンドプロンプトにはき出します。
次のループにより、

０	１	２
2	3	2

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

０	１	２
2	3	3

となります。今度は、２番目のセルと３番目のセルの内容が同じなので、やはり
　　　　　　if(g>0){
　　　　　　　　for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j]){
　　　　　　　　　　　　h=0;
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　}
　　　　　　}
の試験をクリアできません。
これで、f (2)の４回目の歴訪が終わり、f (1)へと帰還します。

０	１	２
2	3

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

０	１	２
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();
　　　　　　　　}
　　　　　　}
の肯定側
　　　　　　if(h==1){
　　　　　　　　if(g+1<n){
　　　　　　　　　　f(g+1);
が実行されf (1)の３度目の来歴となります。

０	１	２
3	i

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

０	１	２
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)の５度目の訪れとなります。

０	１	２
3	1	i

for文によって

０	１	２
3	1	1

０	１	２
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();
　　　　　　　　}
　　　　　　}
の否定部分の命令が遂行され５個目の順列がコマンドプロンプトに出力されます。
以下、

０	１	２
3	1	3

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

０	１	２
3	2

０	１	２
3	2	1

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

０	１	２
3	2	2

０	１	２
3	2	3

０	１	２
3	2

０	１	２
3	3

０	１	２
3

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

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

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

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

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