順列生成アルゴリズムについて仕組みを教えてください
ある本を参考に順列を出力するプログラムを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】**************************
“なぜ連続して呼ばれているのか”の部分が理解できません。予想では、再帰後の部分が一度呼ばれて、このプログラムは止まってしまうと思うですが、最後まで動きます。
なぜ、止まらずに動くのか教えてください。
お礼
ご回答を踏まえてもう一度考えてみたいと思います。 ありがとうございました。