JavaScript再帰関数とは🔁

19131 ワード
webdev programming javascript テキストリンク
再帰は、日常生活の中で多くのアプリケーションを持っている数学的な概念です.
ウェブサイト開発者として、我々は毎日再帰的な機能に遭遇する.
このチュートリアルでは、再帰を使用して解決できる問題のパターンを調べます.
畝

基本概念


function recurse() {
    // 2nd call to itself
    recurse();
}

// 1st call
recurse();
各再帰関数は基本的なケース(終了条件とも呼ばれます)を持っていなければなりません.
function recurse() {
    if (terminate)
        return; // stop calling recurse();

    // continue recurse() if there is no termination
    recurse();
}

recurse();
畝

一方、ループと再帰比較


再帰手法はwhileループに似ています.
あなたが自分で希望の数を乗算する必要があることを想像してX回.
例えば、2 * 2 * 2 = 8畝

一方ループ


function multiply(n, x) {
    let i = 0;
    let res = 1;
    while (i < x) {
      res = res * n;
      i++;
    }
    return res;
}

How does the loop works?


multiply(2,3)

1. i = 0, res = (1) * 2       // 0 < 3 continue ...
2. i = 1; res = (2) * 2       // 1 < 3 continue ...
3. i = 2; res = (2 * 2) * 2   // 2 < 3 continue ...
4. i = 3; res = (2 * 2 * 2)   // 3 < 3 (false) break and return 8
畝

再帰🔁


function multiply(n, x) {
    return x > 1 ? n * multiply(n, x - 1) : n;
}

How does the recursion works?



畝

例


radius 1


URLをエンコードする必要があると仮定しましょう
出力は次のようになります.<html>

ループソリューション


function encode(str, n) {
    let i = 0;
    while (i < n) {
      str = encodeURI(str)
      i++;
    }
    return str;
}

再帰解🔁


function encode(str, n) {
    return n ? encode(encodeURI(str), n - 1) : str;
}
畝

φ2 ( string url decode )


繰り返しエンコードされたURLをデコードする必要があるとしましょう
例えば、以前のURLエンコードされた文字列をとりましょう.%252525253Chtml%252525253E出力結果は以下である

ループソリューション


function decode(str) {
    while (str !== decodeURI(str)) {
      str = decodeURI(str)
    }
    return str;
}

再帰解🔁


function decode(str) {
    return str !== decodeURI(str) ? decode(decodeURI(str)) : str;
}
畝

φ3


あなたのHTMLコードから、%252525253Chtml%252525253Eのような悪いタグを交換する必要があると想像してください
第1例:<html>2件目.
最初のケースでは、次のように簡単にできます.
let html_code = 'hello<script> world<script>';
let output = html_code.replaceAll('<script>','');
// output: hello world
しかし2番目のケースでは失敗します.
let html_code = 'hello<sc<script>ript> world';
let output = html_code.replaceAll('<script>','');
// output: hello<script> world
ここでは回帰が救助に来るところです

再帰解🔁


function clean_html(html, bad_tag) {
    let c_html = html.replaceAll(bad_tag, '');
    return html === c_html ? html : clean_html(c_html, bad_tag)
}

clean_html('hello<sc<script>ript> world', '<script>');

// output: hello world
畝

φ4


この例では、深くネストされた配列でidでカテゴリを見つける必要があります
我々の目標はID番号5のカテゴリです
let the_category_list = [
    {"id" : 1, "name" : "fruits", "child_list" : [
        {"id" : 2, "name" : "apple", "child_list" : [
            {"id" : 4, "name" : "red apple", "child_list" : []},
            {"id" : 5, "name" : "green apple", "child_list" : []}
        ]},
        {"id" : 3, "name" : "banana", "child_list" : []}
    ]}
]

再帰解🔁


function find_cat_by_id(id, category_list) {
    let found_category = false;

    category_list.forEach(cat => {
        if (cat.id === id)
            found_category = cat ;

        if (found_category === false && cat.child_list.length)
            found_category = find_cat_by_id(id, cat.child_list)
    }); 

    return (found_category) ? found_category : false;
}

find_cat_by_id(5, the_category_list)

// Output: {id: 5, name: "green apple", child_list: Array(0)}
畝

残余5


この例では、JavaScriptのFactorialプログラムを再帰的に使用する方法を示します
我々が5の要因を必要とすると想像しましょう:<script>

再帰解🔁


function factorial(x) {
    return x ? x * factorial(x - 1) : 1; 
}
畝

φ6 (再帰を用いたフィボナッチ系列)


この例では、再帰を使用してFibonacciシリーズを印刷するプログラムを書く方法を学びます
フィボナッチシーケンスは以下のように書かれている: hello<script> world<script>

再帰解🔁


function fibonacci(num) {
    return num < 2 ? num : fibonacci(num - 1) + fibonacci(num - 2);
}

function fibonacci_printer(numberOfTerms) {
    let out = [];    for(let i = 0; i < numberOfTerms; i++) {
        out.push(fibonacci(i));
    }    console.log(out.join(', '));
}
このプログラムを使用するには、hello<sc<script>ript>worldを呼び出す必要があります.

Thanks for reading!

More examples will be added later.

Follow me on Twitter -

DTOの可用性
[215]ワインの試飲