はじめに
最近再帰的な実装などを勉強していて、楽しいので実践がてらやってみました。
もっとこう実装した方がいいなどのアドバイスがあればコメントなどでご指摘お願いします。
やりたいこと
下記のように引数に指定した数だけネストしたオブジェクトを作成する関数を実装します。
オブジェクトのプロパティはindexと、ネストしたオブジェクトを保持するnestObjというシンプルなものして、最後の階層になったら、プロパティを持たないオブジェクトをセットするようにします。
後述しますが、最後にはトランポリンで実装してスタックオーバーフローが起きないようにします。
//５階層にネストしたオブジェクトを生成する
let obj = createNestObject(5);
/* 結果
{
index: 0,
nestObj: {
index: 1,
nestObj: {
index: 2,
nestObj: {
index: 3,
nestObj: {
index: 4,
nestObj: {} //最後はプロパティを持たないオブジェクトをセットする
}
}
}
}
}
*/
再帰的に実装する
コードは下記になります。
nestObjプロパティで再帰的にcreateNestObjectを呼び出して、nestNumが0になったときにプロパティを持たないオブジェクト{}を返して処理を終了します。
const createNestObject = (nestNum, idx = 0) => {
if (nestNum === 0) return {}; //nestObjにはプロパティを持たないオブジェクトをセットする
return {
index: idx++, //indexをセットしてからインクリメントする
nestObj: createNestObject(nestNum - 1, idx) //再帰的にメソッドを呼び出す
}
}
let obj = createNestObject(5);
結果
nestNumが0になった時点でプロパティを持たないオブジェクトを返して処理を終了しています。
これで最初にやりたかった実装はすることができました。
内部で何が起きているか
例えば引数に3を指定して内部ではどう処理が行われているかを即時関数で書いてみます。
createNestObject(3);
//内部の処理↓をコピペすればcreateNestObject(3)と同じ動作をします。
((nestNum = 3, idx = 0) => {
if (nestNum === 0) return {}; //nestNumは3の為 false
return {//...................................................................................................................➃
index: idx++, //この時点ではidxは0なので0をセットしてからインクリメントされる
nestObj: ((nestNum = 3 - 1, idx = 1) => { //(nestNum - 1, idx)
if (nestNum === 0) return {}; //nestNumは2の為 false
return {//...........................................................................................................➂
index: idx++, //この時点ではidxは1なので1をセットしてからインクリメントされる
nestObj: ((nestNum = 2 - 1, idx = 2) => { //(nestNum - 1, idx)
if (nestNum === 0) return {}; //nestNumは1の為 false
return {//...................................................................................................➁
index: idx++, //この時点ではidxは2なので2をセットしてからインクリメントされる
nestObj: ((nestNum = 1 - 1, idx = 3) => { //(nestNum - 1, idx)
if (nestNum === 0) return {}; //nestNumは0の為 true プロパティのないオブジェクトを返す。再帰が終了する。...➀
//これより先は実行されない
return {
index: idx++,
nestObj: createNestObject(nestNum, idx)
}
})()
}
})()
}
})()
}
})();
ちょっとわかりずらくなったかもしれませんが、createNestObject(3)を実行したときは上記のような感じで処理が行われます。
➀～➃の順番でオブジェクトがreturnされていくことでネストされたオブジェクトが作られます。
スタックオーバーフロー
しかしこの実装だとある問題があります。
再帰的にメソッドを呼び出すということは引数のnestNumを大きくするとスタックオーバーフローを起こす原因になります。
なぜスタックオーバーフローを起こすかはこの末尾再帰による最適化という記事がわかりやすかったです。
再帰関数は自分自身を再帰的に呼び出すため、関数の呼び出し階層が深くなりがちです。内部的には関数の呼び出しごとにメモリ領域が消費されるため、呼び出し階層が深くなりすぎると実行時エラーが発生する場合があります。
createNestObject(10000) //Uncaught RangeError: Maximum call stack size exceeded
これだとどこでエラーが起きているかわからないのでtry catchでエラーを拾います。
const createNestObject= (nestNum, idx = 0) => {
if (nestNum === 0) return {};
try {
return {
index: idx++, //idxをセットしてからインクリメント
nestObj: createNestObject(nestNum - 1, idx)
}
} catch (e) {
console.log(`error idx is ${idx}`);
}
}
createNestObject(10000)//error idx is 7831
どうやら7831回呼び出された時にスタックオーバーフローが発生しているようです。
トランポリン
これを回避する為にトランポリンという実装方法で実装します。
トランポリンについてはこのJavaScript・再帰・トランポリンという記事がとてもわかりやすかったです。
まずはcreateNestObjectメソッドをcreateNestObject2メソッドに変えます。
そして引数にネストさせるオブジェクトの参照を渡すobj引数を追加します。
トランポリンでは実行する関数を返すのでオブジェクトを返すことができない為、引数に渡されたオブジェクトが変化するようにしました。
const createNestObj2 = (obj, nestNum, idx = 0) => {
if (nestNum === 0) return true; //処理を終了する為にtrueを返す
obj.index = idx++; //idxをセットしてからインクリメント
obj.nestObj = {}; //次に実行されるcreateNestObject2に渡すオブジェクトをセットする
return ()=> createNestObject2(obj.nestObj, nestNum - 1, idx); //引数にネストされたオブジェクトの参照を渡して関数を返す
}
トランポリンの関数を定義します（上記リンクから流用）。
const trampoline = (fn) => {
return (...args) => {
let result = fn(...args);
while (typeof result === 'function') {
result = result();
}
return result;
};
}
定義したトランポリン関数に先ほど定義した関数を渡して実行します。
const tramped = trampoline(createNestObject2);
let obj = {}; //ネストさせるオブジェクトを初期化する
tramped(obj, 10000); //スタックがたまらないのでエラーが起きない
console.log(obj); //1万回ネストされたオブジェクトが出力される
トランポリンで実装することでスタックオーバーフローを起こすことがなくなりました。
なぜスタックオーバーフローを起こさないか
上記のトランポリン実行でなぜスタックオーバーフローを起こさないか細かく見ていきます。
下記のコードでは引数に渡されたcreateNestObject2によってカリー化されます。（この表現あってるのか？）
引数がスプレッド演算子の...argsの為、複数の引数を指定することができます。
const tramped = trampoline(createNestObject2);
//↓と同じ
tramped = (...args) => {//スプレッド演算子により複数の引数を受け取れる
let result = createNestObject2(...args);
while (typeof result === 'function') {
result = result();
}
return result;
};
下記はカリー化したtrampedに引数を指定して実行したときの処理です。
ループで処理が実行される度にcreateNestObject2は関数を返してresultがそれを実行しているので、スタックがたまることがなく、スタックオーバーフローを起こさなくなります。
let obj = {};
tramped(obj, 10000);
//↓と同じ？
((obj, 10000) => {
let result = createNestObj2(obj, 10000); //()=> createNestObj2(obj.nestObj, nestNum - 1, idx);が返される
while (typeof result === 'function') { //resultが関数型の間処理をループする。trueの時処理を抜ける
result = result(); //createNestObj2(obj.nestObj, nestNum - 1, idx);が実行される。
//返り値は()=> createNestObj2(obj.nestObj, nestNum - 1, idx); かtrueが返される
}
return result; //返り値がtrueの時にwhileの処理を抜けるのでtrueを返す
})();
まとめ
これで目的の指定した数だけネストしたオブジェクトを作成することができました。
ただ、トランポリンの実装で引数にオブジェクトの参照を渡す方法しか思いつかなかったのが心残りではあります。
もっとこう実装した方がいいなどありましたら教えてください。
また間違った表現をしているところがあればご指摘ください。