摘要：根據(jù)該規(guī)則，返回第個斐波那契數(shù)。尾遞歸函數(shù)調(diào)用自身，稱為遞歸。一個前端眼中的斐波那契數(shù)列解斐波那契數(shù)列的實用解法調(diào)用棧尾遞歸和手動優(yōu)化尾調(diào)用優(yōu)化譯我從用寫斐波那契生成器中學(xué)到的令人驚訝的件事

斐波那契數(shù)列是以下一系列數(shù)字：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

在種子數(shù)字 0 和 1 之后，后續(xù)的每一個數(shù)字都是前面兩個數(shù)字之和。

斐波那契數(shù)列的一個有趣的性質(zhì)是，數(shù)列的當(dāng)前數(shù)字與前一個數(shù)字的比值無限趨近于黃金分割數(shù)， 1.61803398875…
你可以使用斐波那契數(shù)列來生成各種各樣有趣的東西，比如黃金螺旋 (Golden Spiral)，自然界中存在許多黃金螺旋。

斐波那契數(shù)列（意大利語：Successione di Fibonacci），又譯為費波拿契數(shù)、費氏數(shù)列、黃金分割數(shù)列。

在數(shù)學(xué)上，斐波那契數(shù)列是以遞歸的方法來定義：

F(0)=0, F(1)=1, n>1時，F(xiàn)(n)=F(n-1)+F(n-2)。

根據(jù)該規(guī)則，返回第n個斐波那契數(shù)。

function fibonacci(n) {
    if(n === 0 || n === 1) {
        return n;
    }
    console.log(`fibonacci(${n-1}) + fibonacci(${n-2})`)
    return fibonacci(n - 2) + fibonacci(n - 1)
}
fibonacci(5)

思路：不斷調(diào)用自身方法，直到n為1或0之后，開始一層層返回數(shù)據(jù)。
問題：使用遞歸計算大數(shù)字時，性能會非常低；另外，遞歸造成了大量的重復(fù)計算(很多函數(shù)執(zhí)行了多次)。

從上面代碼的 console 中可以看出，執(zhí)行了許多相同的運算。如果我們對中間求得的變量值，進行存儲的話，就會大大減少函數(shù)被調(diào)用的次數(shù)。
這是典型的以空間換時間。很明顯，函數(shù)被調(diào)用的次數(shù)大大減少，耗時明顯縮減。

let fibonacci = function() {
    let temp = [0, 1];
    return function(n) {
        let result = temp[n];
        if(typeof result != "number") {
            result = fibonacci(n - 1) + fibonacci(n - 2);
            temp[n] = result; // 將每次 fibonacci(n) 的值都緩存下來
        }
        return result;
    }
}(); // 外層立即執(zhí)行

動態(tài)規(guī)劃：從底部開始解決問題，將所有小問題解決掉，然后合并成一個整體解決方案，從而解決掉整個大問題；
遞歸：從頂部開始將問題分解，通過解決掉所有分解的小問題來解決整個問題；

function fibonacci(n) {
    let current = 0;
    let next = 1;
    let temp;
    for(let i = 0; i < n; i++) {
        temp = current;
        current = next;
        next += temp;
    }
    console.log(`fibonacci(${n}, ${next}, ${current + next})`);
    return current;
}

思路：從下往上計算，首先根據(jù)f(0)和f(1)算出f(2),再根據(jù)f(1)和f(2)算出f(3)，依次類推我們就可以算出第n項了。
而這種算法的時間復(fù)雜度僅為O(n)，比遞歸函數(shù)的寫法效率要大大增強。

寫法一：

function fib(n) {
    let current = 0;
    let next = 1;
    for(let i = 0; i < n; i++) {
        [current, next] = [next, current + next];
    }
    return current;
}

[[解構(gòu)賦值]](https://developer.mozilla.org...。因此我們可以用解構(gòu)賦值，省略temp中間變量。

寫法二：

function fib(n) {
    let current = 0;
    let next = 1;
    while(n --> 0) { //     while(n>0) {n--} n--的返回值是n
        [current, next] = [next, current + next];
    }
    return current;
}
fib(10)

// 在ES6規(guī)范中，有一個尾調(diào)用優(yōu)化，可以實現(xiàn)高效的尾遞歸方案。
// ES6的尾調(diào)用優(yōu)化只在嚴(yán)格模式下開啟，正常模式是無效的。
"use strict"
function fib(n, current = 0, next = 1) {
    if(n == 0) return 0;
    if(n == 1) return next; // return next
    console.log(`fibonacci(${n}, ${next}, ${current + next})`);
    return fib(n - 1, next, current + next);
}

=======下面是科普======

什么是尾調(diào)用（函數(shù)式編程的一個重要概念）

一句話，就是指某個函數(shù)的最后一步是調(diào)用另一個函數(shù)。

// 用代碼來說，就是B函數(shù)的返回值被A函數(shù)返回了。
function B() {
    return 1;
}
function A() {
    return B();  // return 1
}

// 尾調(diào)用不一定出現(xiàn)在函數(shù)尾部，只要是最后一步操作即可
function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}

// 下面不屬于尾調(diào)用：調(diào)用函數(shù)g之后，還有別的操作
function f(x){
  let y = g(x);
  return y;
}

function f(x){
  return g(x) + 1;
}

function f(x) {
  g(x); // 這一步相當(dāng)于g(x) return undefined
}

尾調(diào)用優(yōu)化

了解 js 的調(diào)用棧我們知道，當(dāng)腳本要調(diào)用一個函數(shù)時，解析器把該函數(shù)添加到棧中并且執(zhí)行這個函數(shù)，并形成一個棧幀（調(diào)用幀），保存調(diào)用位置和內(nèi)部變量等信息。

如果在函數(shù)A的內(nèi)部調(diào)用函數(shù)B，那么在A的調(diào)用幀上方，還會形成一個B的調(diào)用幀。等到B運行結(jié)束，將結(jié)果返回到A，B的調(diào)用幀才會銷毀。此時如果函數(shù)B內(nèi)部還調(diào)用函數(shù)C，那就還有一個C的調(diào)用幀，以此類推。例如遞歸操作，一個調(diào)用棧中如果保存了大量的棧幀，調(diào)用棧非常長，消耗了巨大的內(nèi)存，會導(dǎo)致爆棧（棧溢出，stack overflow）。后入先出的結(jié)構(gòu)。

尾調(diào)用之所以與其他調(diào)用不同，就在于它的特殊的調(diào)用位置。

那么現(xiàn)在，我們使用尾調(diào)用的話，將函數(shù)B放到了函數(shù)A的最后一步調(diào)用，內(nèi)層函數(shù)不引用外層函數(shù)的變量，就不用保留外層變量的調(diào)用幀了。這樣的話內(nèi)層函數(shù)的調(diào)用幀，會直接取代外層函數(shù)的調(diào)用幀。調(diào)用棧的長度就會小很多。

當(dāng)然，如果內(nèi)層函數(shù)B使用了外層函數(shù)A的變量，那么就仍然需要保留函數(shù)A的棧幀，典型例子即是閉包。

function f() {
  let m = 1;
  let n = 2;
  return g(m + n);
}
f();

這應(yīng)當(dāng)是一次尾調(diào)用。因為m+n的值是通過參數(shù)傳入函數(shù)g內(nèi)部，并沒有直接引用，因此也不能說保存 f 內(nèi)部的變量的值。

下面這種情況內(nèi)層函數(shù)會引用外層函數(shù)的值，所以當(dāng)執(zhí)行到內(nèi)層函數(shù)時外層函數(shù)的調(diào)用幀還會存在與當(dāng)前調(diào)用棧中。

function f() {
  let m = 1;
  let n = 2;
  return function() {
    return m+n;
  };
}
f();

總得來說，如果所有函數(shù)的調(diào)用都是尾調(diào)用，即只保留內(nèi)層函數(shù)的調(diào)用幀，做到每次執(zhí)行時（例如遞歸操作），一個調(diào)用棧中調(diào)用幀只有一項，那么調(diào)用棧的長度就會小很多，這樣需要占用的內(nèi)存也會大大減少。這就是尾調(diào)用優(yōu)化的含義。

什么時候會開啟尾調(diào)用優(yōu)化呢？

在ES5中，尾調(diào)用和其他形式的函數(shù)調(diào)用一樣：腳本引擎創(chuàng)建一個新的函數(shù)棧幀并且壓在當(dāng)前調(diào)用的函數(shù)的棧幀上面。也就是說，在整個函數(shù)棧上，每一個函數(shù)棧幀都會被保存，這有可能造成調(diào)用棧占用內(nèi)存過大甚至溢出。

在ES6中，strict模式下，滿足以下條件，尾調(diào)用優(yōu)化會開啟，此時引擎不會創(chuàng)建一個新的棧幀，而是清除當(dāng)前棧幀的數(shù)據(jù)并復(fù)用：

尾調(diào)用函數(shù)不需要訪問當(dāng)前棧幀中的變量；

尾調(diào)用返回后，函數(shù)沒有語句需要繼續(xù)執(zhí)行；

尾調(diào)用的結(jié)果就是函數(shù)的返回值；

ES6的尾調(diào)用優(yōu)化只在嚴(yán)格模式下開啟，正常模式是無效的。
這是因為在正常模式下，函數(shù)內(nèi)部有兩個變量，可以跟蹤函數(shù)的調(diào)用棧。

arguments：返回調(diào)用時函數(shù)的參數(shù)。
func.caller：返回調(diào)用當(dāng)前函數(shù)的那個函數(shù)。

尾調(diào)用優(yōu)化發(fā)生時，函數(shù)的調(diào)用棧會改寫，因此上面兩個變量就會失真。嚴(yán)格模式禁用這兩個變量，所以尾調(diào)用模式僅在嚴(yán)格模式下生效。

尾遞歸

函數(shù)調(diào)用自身，稱為遞歸。如果尾調(diào)用自身，就稱為尾遞歸。

遞歸非常耗費內(nèi)存，因為需要同時保存成千上百個調(diào)用幀，很容易發(fā)生"棧溢出"錯誤（stack overflow）。但對于尾遞歸來說，由于只存在一個調(diào)用幀，所以永遠(yuǎn)不會發(fā)生"棧溢出"錯誤。

由此可見，"尾調(diào)用優(yōu)化"對遞歸操作意義重大。

遞歸函數(shù)的改寫

尾遞歸的實現(xiàn)，往往需要改寫遞歸函數(shù)，確保最后一步只調(diào)用自身。做到這一點的方法，就是把所有用到的內(nèi)部變量改寫成函數(shù)的參數(shù)。

例如實現(xiàn) fibonacci 函數(shù)需要用到兩個中間變量 current 和 next，那就把這個中間變量改寫成函數(shù)的參數(shù)。

// 實現(xiàn)階乘 復(fù)雜度 O(n)
function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

// 尾遞歸 只保留一個調(diào)用幀，復(fù)雜度 O(1) 
function factorial(n, total = 1) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

問題

在V8引擎層面消除尾遞歸是一個隱式的行為，程序員寫代碼時可能意識不到自己寫了死循環(huán)的尾遞歸，而出現(xiàn)死循環(huán)后又不會報出stack overflow的錯誤，難以辨別。

堆棧信息會在優(yōu)化的過程中丟失，開發(fā)者調(diào)試非常困難。

一個前端眼中的斐波那契數(shù)列
JAVASCRIPT解斐波那契(FIBONACCI)數(shù)列的實用解法
JavaScript 調(diào)用棧、尾遞歸和手動優(yōu)化
尾調(diào)用優(yōu)化
【譯】我從用 JavaScript 寫斐波那契生成器中學(xué)到的令人驚訝的 7 件事