1. isoken26

    Posted

    isoken26
Changes in title
+【JavaScript】引数に指定した数だけネストしたオブジェクトを作成する関数を再帰的に実装する。(トランポリンで実装)
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,206 @@
+# はじめに
+最近再帰的な実装などを勉強していて、楽しいので実践がてらやってみました。
+もっとこう実装した方がいいなどのアドバイスがあればコメントなどでご指摘お願いします。
+
+# やりたいこと
+下記のように引数に指定した数だけネストしたオブジェクトを作成する関数を実装します。
+オブジェクトのプロパティはindexと、ネストしたオブジェクトを保持するnestObjというシンプルなものして、最後の階層になったら、プロパティを持たないオブジェクトをセットするようにします。
+後述しますが、最後にはトランポリンで実装してスタックオーバーフローが起きないようにします。
+
+```js:例
+//5階層にネストしたオブジェクトを生成する
+let obj = createNestObject(5);
+
+/* 結果
+{
+ index: 0,
+ nestObj: {
+ index: 1,
+ nestObj: {
+ index: 2,
+ nestObj: {
+ index: 3,
+ nestObj: {
+ index: 4,
+ nestObj: {} //最後はプロパティを持たないオブジェクトをセットする
+ }
+ }
+ }
+ }
+}
+*/
+```
+
+# 再帰的に実装する
+コードは下記になります。
+`nestObj`プロパティで再帰的に`createNestObject`を呼び出して、`nestNum`が`0`になったときにプロパティを持たないオブジェクト`{}`を返して処理を終了します。
+
+```js:再帰
+const createNestObject = (nestNum, idx = 0) => {
+ if (nestNum === 0) return {}; //nestObjにはプロパティを持たないオブジェクトをセットする
+ return {
+ index: idx++, //indexをセットしてからインクリメントする
+ nestObj: createNestObject(nestNum - 1, idx) //再帰的にメソッドを呼び出す
+ }
+}
+
+let obj = createNestObject(5);
+```
+結果
+<img width="237" alt="スクリーンショット 2018-12-21 19.08.55.png" src="https://qiita-image-store.s3.amazonaws.com/0/117406/76ffc588-4ac4-0704-6a7f-d6ba640e72d4.png">
+
+`nestNum`が0になった時点でプロパティを持たないオブジェクトを返して処理を終了しています。
+これで最初にやりたかった実装はすることができました。
+
+# 内部で何が起きているか
+例えば引数に`3`を指定して内部ではどう処理が行われているかを即時関数で書いてみます。
+
+```js:内部処理
+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を大きくするとスタックオーバーフローを起こす原因になります。
+なぜスタックオーバーフローを起こすかはこの[末尾再帰による最適化](https://qiita.com/pebblip/items/cf8d3230969b2f6b3132)という記事がわかりやすかったです。
+> 再帰関数は自分自身を再帰的に呼び出すため、関数の呼び出し階層が深くなりがちです。内部的には関数の呼び出しごとにメモリ領域が消費されるため、呼び出し階層が深くなりすぎると実行時エラーが発生する場合があります。
+
+```js:スタックオーバーフロー
+ createNestObject(10000) //Uncaught RangeError: Maximum call stack size exceeded
+```
+これだとどこでエラーが起きているかわからないのでtry catchでエラーを拾います。
+
+```js:エラーをキャッチする
+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・再帰・トランポリン](https://qiita.com/41semicolon/items/985bdd2f551d9392463c)という記事がとてもわかりやすかったです。
+
+まずは`createNestObject`メソッドを`createNestObject2`メソッドに変えます。
+そして引数にネストさせるオブジェクトの参照を渡す`obj`引数を追加します。
+トランポリンでは実行する関数を返すのでオブジェクトを返すことができない為、引数に渡されたオブジェクトが変化するようにしました。
+
+```js
+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); //引数にネストされたオブジェクトの参照を渡して関数を返す
+}
+```
+
+トランポリンの関数を定義します(上記リンクから流用)。
+
+```js:トランポリン
+const trampoline = (fn) => {
+ return (...args) => {
+ let result = fn(...args);
+ while (typeof result === 'function') {
+ result = result();
+ }
+ return result;
+ };
+}
+```
+定義したトランポリン関数に先ほど定義した関数を渡して実行します。
+
+```js:トランポリン実行
+
+const tramped = trampoline(createNestObject2);
+let obj = {}; //ネストさせるオブジェクトを初期化する
+tramped(obj, 10000); //スタックがたまらないのでエラーが起きない
+console.log(obj); //1万回ネストされたオブジェクトが出力される
+```
+トランポリンで実装することでスタックオーバーフローを起こすことがなくなりました。
+
+# なぜスタックオーバーフローを起こさないか
+上記の`トランポリン実行`でなぜスタックオーバーフローを起こさないか細かく見ていきます。
+下記のコードでは引数に渡された`createNestObject2`によってカリー化されます。(この表現あってるのか?)
+引数がスプレッド演算子の`...args`の為、複数の引数を指定することができます。
+
+```js
+const tramped = trampoline(createNestObject2);
+//↓と同じ
+tramped = (...args) => {//スプレッド演算子により複数の引数を受け取れる
+ let result = createNestObject2(...args);
+ while (typeof result === 'function') {
+ result = result();
+ }
+ return result;
+ };
+```
+下記はカリー化した`tramped`に引数を指定して実行したときの処理です。
+ループで処理が実行される度に`createNestObject2`は関数を返してresultがそれを実行しているので、スタックがたまることがなく、スタックオーバーフローを起こさなくなります。
+
+```js
+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を返す
+})();
+
+```
+
+
+# まとめ
+これで目的の指定した数だけネストしたオブジェクトを作成することができました。
+ただ、トランポリンの実装で引数にオブジェクトの参照を渡す方法しか思いつかなかったのが心残りではあります。
+もっとこう実装した方がいいなどありましたら教えてください。
+また間違った表現をしているところがあればご指摘ください。
+
+# 参考サイト
+- [JavaScript・再帰・トランポリン](https://qiita.com/41semicolon/items/985bdd2f551d9392463c)
+- [末尾再帰による最適化](https://qiita.com/pebblip/items/cf8d3230969b2f6b3132)
+- [How to understand trampoline in JavaScript?](https://stackoverflow.com/questions/25228871/how-to-understand-trampoline-in-javascript/27704484#27704484)