順列生成アルゴリズムについて仕組みを教えてください

質問

ある本を参考に順列を出力するプログラムをJavaScript用に書き直しました。
上手く動いたのですが、どうして、順列を出力できるのか理解できません。

まず、プログラムは以下になります。
<script>
// 対象の配列
var array = [0,1,2,3];
// 配列の数
var N = array.length;
// 順列を出力するプ関数
function permutation( n ) {
//　テンポラリー用
var temp;

// 順列を生成する処理部分
if ( n < N ) {

for ( var i = n; i < N; i++ ) {
// （1）対象の配列から数字を一つ取り出して、他の数字と入れかえる
temp = array[n];
array[n] = array[i];
array[i] = temp;

// （2）再起呼び出し
permutation( n + 1 );
// （3）入れ替えた数字を元に戻す
temp = array[n];
array[n] = array[i];
array[i] = temp;
}
} else {
// 出力
console.log( "結果：" + array);
}
}

// エントリーポイント
permutation(0);
</script>

処理を理解するために、コメントの（1）や（3）などに console.log を入れて、出力したところ、全く理解できないスタックの流れになっていました。

具体的には、1～2を条件を満たす間繰り返した後、一度出力（スタック開放）します。その後、（3）の処理をするのですが、その直ぐ後に、また（3）の処理をするのです。
具体的なログは以下のようになりました。

【n=0】**************************// 関数の呼出しと呼出し時の引数です。
i=0
　再帰前:1回:0,1,2,3 n=0　　　　　　// （1）の処理です。0,1,2,3は、対象の配列です。
【n=1】**************************
i=1
　再帰前:2回:0,1,2,3 n=1
【n=2】**************************
i=2
　再帰前:3回:0,1,2,3 n=2
【n=3】**************************
i=3
　再帰前:4回:0,1,2,3 n=3
【n=4】**************************
スタック開放：0,1,2,3 n=4

　　再帰後:1回:0,1,2,3 n=3　　　　　// （3）の処理です。
　　再帰後:2回:0,1,2,3 n=2　　　　　// なぜ連続して呼ばれているのか
i=3
　再帰前:5回:0,1,3,2 n=2
【n=3】**************************
i=3
　再帰前:6回:0,1,3,2 n=3
【n=4】**************************
スタック開放：0,1,3,2 n=4

　　再帰後:3回:0,1,3,2 n=3
　　再帰後:4回:0,1,2,3 n=2　　　　　// なぜ連続して呼ばれているのか
　　再帰後:5回:0,1,2,3 n=1　　　　　// なぜ連続して呼ばれているのか
i=2
　再帰前:7回:0,2,1,3 n=1
【n=2】**************************

“なぜ連続して呼ばれているのか”の部分が理解できません。予想では、再帰後の部分が一度呼ばれて、このプログラムは止まってしまうと思うですが、最後まで動きます。
なぜ、止まらずに動くのか教えてください。

回答No.2

kmee · ベストアンサー

「再帰呼び出し」そのものについて、理解できていますか?
・まったく別の関数を呼び出しているつもりになる
・機能だけで考える
というあたりがコツだと思ってます。
ループ同じように同じ行を行ったり来たり、と考えていると理解できません。

function partition_0() {
for ( var i = 0; i < N; i++ ) {
// （1）対象の配列から数字を一つ取り出して、他の数字と入れかえる
Swap(i,0)
// （2）呼び出し
permutation_1();
// （3）入れ替えた数字を元に戻す
Swap(i,0)
}

function partition_1() {
for ( var i = 1; i < N; i++ ) {
// （1'）対象の配列から数字を一つ取り出して、他の数字と入れかえる
Swap(i,1)
// （2'）呼び出し
permutation_2();
// （3'）入れ替えた数字を元に戻す
Swap(i,1)
}

と考えます
すると、(2)で呼び出された partition_1 で(3')を実行したあと、戻ってきたpartition_0の(3)が実行される、ということがわかるかと思います。
同じ「関数」で連続実行されているわけではありません。
「別の関数」でたまたま同じような動きがあったために、連続実行しているように見えるだけです。

順列になる理由ですが
a0,a1,...,aN
の順列は次のようにして求められます。
(1)N=0 なら
a0
の一通りだけです。
(2)N>0 なら
a0 + (a0以外の順列)
a1 + (a1以外の順列)
...
aN + (aN以外の順列)
となります。ここで、(a0以外の順列)、(a1以外の順列) .. を求めるのに、今示した「順列の求め方」を使います。

お礼

ありがとうございました。
> まったく別の関数を呼び出しているつもりになる
は、盲点でした！

自分の中で、再帰呼び出しと繰り返し処理を同じ次元で捉えていました。

仰るとおり、別の関数として呼び出していると捉えますとログの通りの処理になりました！！

3日悩んでいたので、とてもスッキリしました。
今度からは、kmeeさんから教わった考え方で、再帰呼び出しを使っていこうと思います。
本当にありがとうございました！！！

回答No.1

Tasuke22

それは連続して呼ばれているのではなく、
連続して帰っているのです。

呼ばれた分、帰らなくてはなりませんから。

お礼

「再帰呼び出し」と書くとつい呼び出し側を注視してしまって、繰り返し処理のように捉えてしまいます。

「再帰」ということはどういうことか、もう一度良く考えてみようと思います。

ありがとうございました。