組み合わせを再帰で作るときの考え方

CodeIQで組み合わせを作らなきゃいけない問題があって、その問題がJavaScriptで解かなきゃいけないから、それを考えていた。
前に、ハノイの塔のプログラムを作ったおかげで、再帰についての考え方はなんとなくわかった。要は「数学的帰納法」。これの考え方が身についているか。

さて、組み合わせについて考える。こういう時はまず1の時から見る。1の時は、

  ＜＜１＞＞

を返せばいい。さて、2からはどうか。これも当たり前で、

　＜＜1,2＞,＜2，1＞＞

でおｋ。
さて、このときどのような変化が起こっているのだろう?それが最も大事だ。
そこで行き着いた考えがこれだ。
"n-1で出た結果のそれぞれの配列の順番1つずつに新しい値を挿入する"
自分で説明しててもこれはわかりにくい日本語だから図で解説。

これは、n=2のとき。次の3にするには、2個の要素に3を入れるべき個所が3か所ある。
それを埋めていけばいいわけだ。
プログラムが以下。

    var makeComb = function(n) {

        if ( n == 1 ) {

            return 1;

        }

        var prevComb = makeComb(n - 1);

        var currComb = [];

        for (i = 0; i < prevComb.length; i++) {

            for (j = 0; j < prevComb[i].length + 1; j++) {

                var copied = prevComb[i].concat();

                copied.splice(j, 0, n);

                currComb.push(copied);

            }

        }

        return currComb;

    };

なんかJavaScriptの参照が色々うざく、そしてspliceメソッドが意味不明な戻り値を返すので、オブジェクトのコピーをconcat()でやっている。
まぁそれ以外は、読めるコードなんじゃないだろうか。
こうなるとnがめっちゃ大きくなったときとか考えなきゃいけないんだろうけど、とりあえずはいいや。