多重forは再帰で書ける

(追記)
AtCoderのABC165のC問題を再帰と多重forで解いた。
再帰
https://atcoder.jp/contests/abc165/submissions/12674026
・多重for
https://atcoder.jp/contests/abc165/submissions/12686227
(追記ここまで)

C++で、1〜4の数字を1回ずつ使った4桁の数を出力する。

const int N = 4;
void hoge1()
{
    int p[N] = {};
    for (int i4 = 0; i4 < N; i4++){
        if (p[i4]) continue;
        p[i4] = 1;
        for (int i3 = 0; i3 < N; i3++){
            if (p[i3]) continue;
            p[i3] = 1;
            for (int i2 = 0; i2 < N; i2++){
                if (p[i2]) continue;
                p[i2] = 1;
                for (int i1 = 0; i1 < N; i1++){
                    if (p[i1]) continue;
                    printf("%d\n", (i4+1)*1000 + (i3+1)*100 + (i2+1)*10 + (i1+1));
                }
                p[i2] = 0;
            }
            p[i3] = 0;
        }
        p[i4] = 0;
    }
}

この4重のfor文は、読みにくいわけではないが、書くのが面倒だ。
また、Nを4から5に変更したいときにも、手間がかかる。
そこで、再帰を使って書き直す。

const int N = 4;
void fuga(int _d)
{
    static int p[N] = {}, q[N];
    int d = _d - 1;
    for (int i = 0; i < N; i++){
        if (p[i]) continue;
        q[d] = i + 1;
        if (d == 0){
            printf("%d\n", q[3]*1000 + q[2]*100 + q[1]*10 + q[0]);
            continue;
        }
        p[i] = 1;
        fuga(d);
        p[i] = 0;
    }
}
void hoge2()
{
    fuga(N);
}

以下が出力。hoge1()とhoge2()は同じものを出力する。

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321