Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

【JavaScript】指定した数だけネストしたオブジェクトを作成する関数を再帰的に実装する。(トランポリンで実装)

More than 1 year has passed since last update.

 はじめに

最近再帰的な実装などを勉強していて、楽しいので実践がてらやってみました。
もっとこう実装した方がいいなどのアドバイスがあればコメントなどでご指摘お願いします。

 やりたいこと

下記のように引数に指定した数だけネストしたオブジェクトを作成する関数を実装します。
オブジェクトのプロパティはindexと、ネストしたオブジェクトを保持するnestObjというシンプルなものして、最後の階層になったら、プロパティを持たないオブジェクトをセットするようにします。
後述しますが、最後にはトランポリンで実装してスタックオーバーフローが起きないようにします。

//5階層にネストしたオブジェクトを生成する
let obj = createNestObject(5);

/* 結果
{
    index: 0,
    nestObj: {
        index: 1,
        nestObj: {
            index: 2,
            nestObj: {
                index: 3,
                nestObj: {
                    index: 4,
                    nestObj: {} //最後はプロパティを持たないオブジェクトをセットする
                 }
             }
        }
    }
}
*/

再帰的に実装する

コードは下記になります。
nestObjプロパティで再帰的にcreateNestObjectを呼び出して、nestNum0になったときにプロパティを持たないオブジェクト{}を返して処理を終了します。

再帰
const createNestObject = (nestNum, idx = 0) => { 
    if (nestNum === 0) return {}; //nestObjにはプロパティを持たないオブジェクトをセットする
    return {
        index: idx++, //indexをセットしてからインクリメントする
        nestObj: createNestObject(nestNum - 1, idx) //再帰的にメソッドを呼び出す
    }
}

let obj = createNestObject(5);

結果
スクリーンショット 2018-12-21 19.08.55.png

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を返す
})();

まとめ

これで目的の指定した数だけネストしたオブジェクトを作成することができました。
ただ、トランポリンの実装で引数にオブジェクトの参照を渡す方法しか思いつかなかったのが心残りではあります。
もっとこう実装した方がいいなどありましたら教えてください。
また間違った表現をしているところがあればご指摘ください。

 参考サイト

isoken26
4年目エンジニア/文章書くのが苦手なのでアウトプットして練習 TypeScript/JavaScript 配列操作が好き
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away