JavaScriptデータ構造とアルゴリズム-再帰的

1.再帰
再帰的には問題を解決する方法であり、問題を解決する小さい部分から最大の問題を解決するまで、関数呼び出し自体を含む.操作ツリーとデータ構造を簡単にすることができます.自身の関数または方法を直接呼び出します.

function recursiveFunction(someParam) {
     
    recursiveFunction(someParam);
}

自身の関数を間接的に呼び出します.

function recursiveFunction1(someParam) {
     
    recursiveFunction2(someParam);
}

function recursiveFunction2(someParam) {
     
    recursiveFunction1(someParam);
}

もしrecursive Functionを実行すれば、結果はずっと実行し続けます.したがって、各再帰関数は、無限再帰性を防ぐために、基線条件、すなわち再帰的に呼び出されない条件(停止点)を持つ必要がある.
2.階乗を計算する
2.1反復階乗
(n)*(n-1)*(n-2)*(n-3)**1

function factorialIterative(number) {
     
    if (number < 0) return undefined;
    let total = 1;
    for (let n = numbe; n > 1; n--) {
     
        total = total * n;
    }
    return total;
}
console.log(factorialIterative(5));

2.2再帰階乗

function factorial(n) {
     
    //     
    if (n === 1 || n === 0) {
     
        return 1;
    }
    //     
    return n * factorial(n - 1);
}
console.log(factorial(5));

が再帰されると、各関数呼び出しは、コールスタックの上部にスタックされる.これは、各呼び出しは、前の呼び出しの結果に依存する可能性があるからである.

もしベースラインの条件がないならば、再帰も無限に実行し続けることはできなくて、ブラウザーは誤りを投げ出すことができて、つまりスタックは誤りをあふれ出して、すべてのブラウザーがすべて自分のブラウズの上限があるためです.

3.フィボナッチ数列
フィボナッチの数列は0、1、1、2、3、5、8、13、21、34などの数からなるシーケンスです.
3.1反復

function fibonacciIterative(n) {
     
    if (n < 1) return 0;
    if (n <= 2) return 1;

    let fibNMinus2 = 0;
    let fibNMinus1 = 1;
    let fibN = n;
    for (let i = 2; i <= n; i++) {
     
        fibN = fibNMinus1 + fibNMinus2;
        fibNMinus2 = fibNMinus1;
        fibNMinus1 = fibN;
    }
    return fibN;
}

3.2再帰

function fibonacci(n) {
     
    //     
    if (n < 1) return 0;
    if (n <= 2) return 1;
    //   n > 2         
    return fibonacci(n - 1) + fibonacci(n - 2);
}

3.3記憶化フィボナッチ数
メモリ化は、前の結果を保存する値を最適化する技術であり、キャッシュと同様である.

function fibonacciMemoization(n) {
     
    //     memo            
    const memo = [0, 1];
    const fibonacci = (n) => {
     
        //         ，    
        if (memo[n] != null) return memo[n];
        //               
        return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    };
    return fibonacci;
}

再帰と反復の比較:

反復は再帰よりもずっと速いです.

の再帰がより分かりやすく、必要なコードも一般的に

より少ない.

は、いくつかのアルゴリズムにとっては、反復の解法は利用できないかもしれないし、テールコール最適化があり、再帰的な余分な消費は、

を除去することもできる.