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

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

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

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

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

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

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

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

根據(jù)該規(guī)則，返回第n個(gè)斐波那契數(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之后，開(kāi)始一層層返回?cái)?shù)據(jù)。
問(wèn)題：使用遞歸計(jì)算大數(shù)字時(shí)，性能會(huì)非常低；另外，遞歸造成了大量的重復(fù)計(jì)算(很多函數(shù)執(zhí)行了多次)。

從上面代碼的 console 中可以看出，執(zhí)行了許多相同的運(yùn)算。如果我們對(duì)中間求得的變量值，進(jìn)行存儲(chǔ)的話，就會(huì)大大減少函數(shù)被調(diào)用的次數(shù)。
這是典型的以空間換時(shí)間。很明顯，函數(shù)被調(diào)用的次數(shù)大大減少，耗時(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) 的值都緩存下來(lái)
        }
        return result;
    }
}(); // 外層立即執(zhí)行

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

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ì)算，首先根據(jù)f(0)和f(1)算出f(2),再根據(jù)f(1)和f(2)算出f(3)，依次類推我們就可以算出第n項(xiàng)了。
而這種算法的時(shí)間復(fù)雜度僅為O(n)，比遞歸函數(shù)的寫(xiě)法效率要大大增強(qiáng)。

寫(xiě)法一：

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中間變量。

寫(xiě)法二：

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ī)范中，有一個(gè)尾調(diào)用優(yōu)化，可以實(shí)現(xiàn)高效的尾遞歸方案。
// ES6的尾調(diào)用優(yōu)化只在嚴(yán)格模式下開(kāi)啟，正常模式是無(wú)效的。
"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ù)式編程的一個(gè)重要概念）

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

// 用代碼來(lái)說(shuō)，就是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)用一個(gè)函數(shù)時(shí)，解析器把該函數(shù)添加到棧中并且執(zhí)行這個(gè)函數(shù)，并形成一個(gè)棧幀（調(diào)用幀），保存調(diào)用位置和內(nèi)部變量等信息。

如果在函數(shù)A的內(nèi)部調(diào)用函數(shù)B，那么在A的調(diào)用幀上方，還會(huì)形成一個(gè)B的調(diào)用幀。等到B運(yùn)行結(jié)束，將結(jié)果返回到A，B的調(diào)用幀才會(huì)銷毀。此時(shí)如果函數(shù)B內(nèi)部還調(diào)用函數(shù)C，那就還有一個(gè)C的調(diào)用幀，以此類推。例如遞歸操作，一個(gè)調(diào)用棧中如果保存了大量的棧幀，調(diào)用棧非常長(zhǎng)，消耗了巨大的內(nèi)存，會(huì)導(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)用幀，會(huì)直接取代外層函數(shù)的調(diào)用幀。調(diào)用棧的長(zhǎng)度就會(huì)小很多。

當(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)用。因?yàn)閙+n的值是通過(guò)參數(shù)傳入函數(shù)g內(nèi)部，并沒(méi)有直接引用，因此也不能說(shuō)保存 f 內(nèi)部的變量的值。

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

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

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

什么時(shí)候會(huì)開(kāi)啟尾調(diào)用優(yōu)化呢？

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

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

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

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

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

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

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

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

尾遞歸

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

遞歸非常耗費(fèi)內(nèi)存，因?yàn)樾枰瑫r(shí)保存成千上百個(gè)調(diào)用幀，很容易發(fā)生"棧溢出"錯(cuò)誤（stack overflow）。但對(duì)于尾遞歸來(lái)說(shuō)，由于只存在一個(gè)調(diào)用幀，所以永遠(yuǎn)不會(huì)發(fā)生"棧溢出"錯(cuò)誤。

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

遞歸函數(shù)的改寫(xiě)

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

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

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

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

問(wèn)題

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

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

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