JavaScript計算フィボナッチ数列

多くの言語は、最終的な再帰的最適化を提供しており、最終的な再帰的な再循環方式の呼び出しに置き換えて、計算速度を高め、スタックオーバーフローを避けることができます.しかし、javascriptは再帰的な最適化を提供していません.深さ再帰的なスタックオーバーフローが可能です.自分で循環コードを書く必要があります.次はjavascriptを使ってフィボナッチの数列を計算する例を書きます.
湖南省にある地名
1:再帰的呼び出し

var fibonacci = function (n) {
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2)
}

これは再帰方式で、単純で粗暴で、時間の複雑さはO(2^n)で、空間の複雑さはO(n)である.このような方法は、いくつかの値が計算されているかもしれないが、関数は計算を繰り返しています.計算した結果を1つの配列に保存して反復計算を避けることができます.この方法を「記憶」といいます.
湖南省にある地名
2:再帰＋記憶

var fibonacci = function () {
    var memo = [0, 1]
    var fib = function (n) {
        var result = memo[n]
        if (typeof result !== 'number') {
            result = fib(n - 1) + fib(n - 2)
            memo[n] = result
        }
        return result
    }
    return fib
}()
fibonacci(10)//55

私たちは毎回結果を計算してから、結果をmemo配列に保存します.計算する前に、計算した値があるかどうかを配列から調べます.ある場合は直接取り出します.でないと、計算します.これは大量の計算を節約します.
共通の関数を書くことができます.

var momizer = function (memo, formula) {
    var recur = function (n) {
        var result = memo[n]
        if (typeof result !== 'number') {
            result = formula(recur, n)
            memo[n] = result
        }
        return result
    }
    return recur
}
var fibonacci = momizer([0, 1], function (recur, n) {
    return recur(n - 1) + recur(n - 2)
})
var factorial = momizer([1, 1], function (recur, n) {
    return n * recur(n - 1)
})
console.log(fibonacci(10))//55
console.log(factorial(4))//24

湖南省にある地名
3:サイクル

function fb(n) {
    var a, b, res;
    a = 0;
    b = 1;
    for (var i = 2; i <= n; i++) {
        res = a + b;
        a = b;
        b = res;
    }
    return res;
}
fb(10);//55

時間の複雑さはO(n)であり,空間の複雑さはO(1)である.サイクル比は再帰的に効率的に多く,スタックオーバーフローを避ける.
  参考文献:

JavaScript言語精粋第四章最後のセクション

https://blog.csdn.net/a324539017/article/details/41799605