アルゴリズム: Javascript をエレガントに使用して構造ツリーを再帰的に描画する方法

[[376839]]

再帰と末尾再帰

簡単に言えば、再帰とは関数が自分自身を呼び出すことです。プログラミング言語のアルゴリズムとして広く使用されています。中心となる考え方は、大規模で複雑な問題を段階的に元の問題に似たより小さな問題に変換して解決することです。一般的に、再帰には境界条件、再帰的な前進フェーズ、および再帰的な戻りフェーズが必要です。境界条件が満たされない場合は再帰が前進し、境界条件が満たされた場合は再帰が戻ります。

しかし、有能なプログラマーとして、再帰アルゴリズムは通常のループなどの一般的に使用されるアルゴリズムよりも効率が低いことも知っておく必要があります。したがって、より優れたアルゴリズムがない場合、または特定の状況で再帰の方が適切な場合を除き、再帰は可能な限り避けるべきです。再帰呼び出しプロセス中、システムはスタックを開いて、各レイヤーの戻りポイント、ローカル量などを保存します。再帰回数が多すぎると、スタック オーバーフローが簡単に発生する可能性があります。

このとき、末尾再帰を使用する必要があります。つまり、関数内のすべての再帰呼び出しは、関数の最後に表示されます。末尾再帰の場合、呼び出しレコードは 1 つしかないため、「スタック オーバーフロー」エラーは発生しません。

関数階乗(n) {
  (n === 1)の場合は1を返します。
 n * 階乗(n - 1)を返します。
 } 
 
階乗(5) // 120

最大で n 個のコールスタックを保存する必要があり、その複雑さは O(n) です。末尾再帰を使用する場合:

関数階乗(n, 合計 = 1) {
  if (n === 1) 合計を返します。
階乗を返します(n - 1, n * 合計);
 } 
 
階乗(5) // 120

この時点では、保存する必要がある呼び出しスタックは 1 つだけであり、複雑さは O(1) です。今回の事例を通じて、その本質が徐々に理解できたでしょうか？次に、再帰アプリケーションのよく使われる事例をいくつか紹介し、その後、この記事のタイトルで説明したツリーを実装していきます。

再帰の一般的な応用例

1. 配列の合計

指定された配列 arr について、arr 内のすべての項目の合計を計算します。

関数sumArray(arr, total) {
    （arr.length === 1）の場合{
合計を返す
    }
戻る 合計(arr、合計 + arr.pop())
 } 
 
 arr = [1,2,3,4]とします。
合計配列(arr, arr[1]) // 10

このメソッドは、配列パラメータと初期値（配列の最初の項目）を関数に渡し、反復処理を通じて配列の合計を実装します。

2. フィボナッチ数列

フィボナッチ数列は黄金比数列とも呼ばれ、1、1、2、3、5、8、13、21、34、... という数列を指します。数学では、フィボナッチ数列は次のように再帰的に定義されます。F(1)=1、F(2)=1、F(n)=F(n-1)+F(n-2)(n>=3、n∈N*)。フィボナッチ数列は、現代物理学、準結晶構造、化学などの分野に直接応用されています。次に、js を使用して n 番目のフィボナッチ数を見つけるメソッドを実装します。

 //フィボナッチ数列
関数階乗1(n) {
    (n <= 2)の場合{
戻り値1
    }
階乗1(n-1) + 階乗1(n-2)を返す
} 
 
 // 末尾再帰最適化後
関数factorial2 (n, 開始 = 1, 合計 = 1) {
    (n <= 2)の場合{
合計を返す
    }
階乗2を返す(n -1, 合計, 合計 + 開始)
 }

末尾再帰最適化関数からは、関数自体が呼び出されるたびに更新された初期値と最終結果が渡され、バックトラックによって最終結果が得られることがわかります。

3. 階乗

階乗については上で説明しました。確認したい場合は、上にスクロールしてください。

4. 省と市のカスケード多階層連携

省市カスケード多階層リンク方式の本質は、構造化されたデータ構造を生成することです。elementやantdには対応する実装があるので、ここでは詳しく紹介しません。

5. ディープコピー

ディープコピーの例は誰もがよく知っているので、ここでは単純な実装のアイデアを示します。

関数クローン(ターゲット) {
   if (typeof ターゲット === 'オブジェクト' ) {
       cloneTarget を Array.isArray(target) とします。[] : {};
 for (constキー ターゲット内）{
           cloneTarget[キー] = clone(target[キー]);
       }
 cloneTargetを返します。
   }それ以外{
ターゲットを返します。
   }
 };

6. はしご問題

全部で n 段の階段があります。一度に上れるのは 1 段か 2 段だけです。この階段を上るには、何通りの方法があるでしょうか。

 n =1; 結果 = 1 --> 1  
 n =2; 結果 = 2 --> 11 2  
 n =3; 結果 = 3 --> 111 12 21  
 ...
最初のステップが 1 ステップ歩くことである場合、上記の規則は、残りのステップを歩くには n-1 通りの方法があることを示しています。
最初のステップが 2 歩歩くことである場合、上記の規則は、残りのステップを歩くには n-2 通りの方法があることを示しています。
全部でfn(n-1) + fn(n-2)通りの方法がある
関数ステップ(n) {
    n <= 1の場合{
戻り値1
    }
ステップ(n-1) + ステップ(n-2)を返す
}

7. オブジェクトデータのフォーマット

この質問は、私が Alibaba で面接を受けたときの筆記試験の質問でした。質問は、「サーバーがネストされたオブジェクトを返す場合、オブジェクトのキー名の大文字と小文字は不明です。キー名を小文字で統一するにはどうすればよいですか?」というものでした。

 obj = {
    a: '1' 、
    b: {
        c: '2' ,
        D: {
            E: '3'  
        }
    }
 }
以下のように変換されます。
 obj = {
    a: '1' 、
    b: {
        c: '2' ,
        d: {
            e: '3'  
        }
    }
 } 
 
 // コード実装
関数keysLower(obj) {
    reg = new RegExp( "([AZ]+)" , "g" );
 for (letキー  obj内）{
        if (obj.hasOwnProperty(キー)) {
            temp = obj[キー]とします。
            if (reg.test(キー.toString())) {
                // 変更された属性名をtempに再割り当てし、変換された属性をオブジェクト obj に追加します。
 temp = obj[ key . replace (reg, function (result) {
結果を返す.toLowerCase()
                })] = obj[キー];
                // 以前大文字だったキー属性を削除します
obj[キー]を削除します。
            }
            // 属性がオブジェクトまたは配列の場合は、関数を再実行します
            if (typeof temp === 'object' || Object.prototype.toString.call( temp ) === '[object Array]' ) {
                keysLower( temp );
            }
        }
    }
 objを返します。
 };

具体的なプロセスや考え方はコード内に注釈が付けられています。興味があれば、自分で勉強することもできます。

8. ディレクトリを走査/削除する

ここではディレクトリを削除するために node を使用します。既存の node API にはディレクトリを削除する機能がありますが、ディレクトリ内にファイルやサブディレクトリがある場合、fs.rmdir && fs.rmdirSync ではそれらを削除できません。そのため、まずディレクトリ内のファイルを削除してから、フォルダを削除する必要があります。

関数deleteFolder(パス) {
    var ファイル = [];
    if(fs.existsSync(path)) { // ディレクトリが存在する場合
        ファイル = fs.readdirSync(パス);
        files.forEach(関数(ファイル,インデックス) {
            var curPath = パス + "/" + ファイル;
            if(fs.statSync(curPath).isDirectory()) { // ディレクトリの場合は再帰的に
                フォルダーを削除します(現在のパス);
            } else { // ファイルを削除する
                fs.unlinkSync(curPath);
            }
        });
        fs.rmdirSync(パス);
    }
 }

9. フラクタルグラフィックを描く

再帰を使用すると、グラフィックスの自由度が高まりますが、これが最善の選択ではないことに注意してください。

いくつかのツールと再帰的な思考を使用することで、上記のフラクタル パターンを実現できます。

10. 配列のフラット化

配列のフラット化とは、次の例に示すように、ネストされた配列を単一の配列に拡張することを意味します。

 a = [1,2,3, [1,2,3, [1,2,3]]] とする
// は
a = [1,2,3,1,2,3,1,2,3]とする
// 具体的な実装
関数flat(arr = [], 結果 = []) {
    arr.forEach(v => {
        Array.isArray(v) の場合
            結果 = result.concat(flat(v, []))
        }それ以外{
            結果.push(v)
        }
    })
結果を返す
} 
 
平らな

もちろん、これは私が実装した方法の 1 つに過ぎず、他にも実装方法はたくさんあり、皆さんもぜひ試してみてください。

再帰を使用してカスタムスタイルの構造ツリーを描画する

上記の紹介を通じて、再帰とその応用の基本的な概念を皆さんは理解できたと思います。次に、再帰を使用して構造ツリーを描く方法を段階的に説明します。効果画像:

この図は、ディレクトリ構造に基づいて生成されたディレクトリ ツリー図です。多くのアプリケーション シナリオで広く使用されています。次に、その実装プロセスを見てみましょう。

定数 fs = require( 'fs' )
定数パス = require( 'パス' )
 // ディレクトリをトラバース/ディレクトリツリーを生成する
関数treeFolder(パス、フラグ = '|_' ) {
    var ファイル = []; 
     
    if (fs.existsSync(パス)) {
        ファイル = fs.readdirSync(パス);
        files.forEach(関数(ファイル,インデックス) {
            var curPath = パス + "/" + ファイル;
            if(fs.statSync(curPath).isDirectory()) { // 再帰
                // obj[file] = treeFolder(curPath, {});
                console.log(フラグ、ファイル)
                ツリーフォルダ(curPath, ' ' + フラグ)
            }それ以外{
                // obj[ '--' ] = ファイル
                console.log(フラグ、ファイル)
            }
        })
        //オブジェクトを返す
    }
 } 
 
ツリーフォルダー(path.resolve(__dirname, './test' ))

Test は、次のように構築したテスト ディレクトリです。

わずか 12 行のコードで構造ツリーを生成する小さなアプリケーションを実装しました。再帰は興味深いと思いませんか? この関数では、最初のパラメーターはディレクトリの絶対パスで、2 番目は識別子です。識別子によって、生成されたブランチのスタイルが決まります。さまざまなスタイルをカスタマイズできます。