斐波那契數列 · 前端筆記

[TOC] # 概念斐波那契數列是以下一系列數字： > 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數字 0 和 1 之后，后續的每一個數字都是前面兩個數字之和。 斐波那契數列的一個有趣的性質是，數列的當前數字與前一個數字的比值無限趨近于黃金分割數， 1.61803398875… 你可以使用斐波那契數列來生成各種各樣有趣的東西，比如黃金螺旋 (Golden Spiral)，自然界中存在許多黃金螺旋。 ![](https://img.kancloud.cn/67/04/6704a18268e8a66fc5d6d2b53a33bca5_1200x675.png) 斐波那契數列（意大利語：Successione di Fibonacci），又譯為費波拿契數、費氏數列、黃金分割數列。 在數學上，斐波那契數列是以遞歸的方法來定義： > F(0)=0, F(1)=1, n>1時，F(n)=F(n-1)+F(n-2)。 根據該規則，返回第n個斐波那契數。 # 實現 ## 遞歸法 ~~~jsx 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) ~~~ 思路：不斷調用自身方法，直到n為1或0之后，開始一層層返回數據。問題：使用遞歸計算大數字時，性能會非常低；另外，遞歸造成了大量的重復計算(很多函數執行了多次)。 ## 數組緩存從上面代碼的 console 中可以看出，執行了許多相同的運算。如果我們對中間求得的變量值，進行存儲的話，就會大大減少函數被調用的次數。這是典型的以空間換時間。很明顯，函數被調用的次數大大減少，耗時明顯縮減。 ~~~jsx 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; } }(); // 外層立即執行 ~~~ ## 遞推法（動態規劃）動態規劃：從底部開始解決問題，將所有小問題解決掉，然后合并成一個整體解決方案，從而解決掉整個大問題；遞歸：從頂部開始將問題分解，通過解決掉所有分解的小問題來解決整個問題； ~~~jsx 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; } ~~~ 思路：從下往上計算，首先根據f(0)和f(1)算出f(2),再根據f(1)和f(2)算出f(3)，依次類推我們就可以算出第n項了。而這種算法的時間復雜度僅為O(n)，比遞歸函數的寫法效率要大大增強。 1. 寫法一： ~~~jsx function fib(n) { let current = 0; let next = 1; for(let i = 0; i < n; i++) { [current, next] = [next, current + next]; } return current; } ~~~ [\[解構賦值\]](https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment)允許我們將值直接從數組中提取到不同變量中。因此我們可以用解構賦值，省略temp中間變量。 2. 寫法二： ~~~jsx 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) ~~~ ## 尾調用優化 ~~~jsx // 在ES6規范中，有一個尾調用優化，可以實現高效的尾遞歸方案。 // ES6的尾調用優化只在嚴格模式下開啟，正常模式是無效的。 '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); } ~~~ * * * \=======下面是科普====== # 什么是尾調用一句話，就是指某個函數的最后一步是調用另一個函數。 ~~~jsx // 用代碼來說，就是B函數的返回值被A函數返回了。 function B() { return 1; } function A() { return B(); // return 1 } // 尾調用不一定出現在函數尾部，只要是最后一步操作即可 function f(x) { if (x > 0) { return m(x) } return n(x); } // 下面不屬于尾調用：調用函數g之后，還有別的操作 function f(x){ let y = g(x); return y; } function f(x){ return g(x) + 1; } function f(x) { g(x); // 這一步相當于g(x) return undefined } ~~~ # 尾調用優化了解 js 的調用棧我們知道，當腳本要調用一個函數時，解析器把該函數添加到棧中并且執行這個函數，并形成一個棧幀（調用幀），保存調用位置和內部變量等信息。 如果在函數A的內部調用函數B，那么在A的調用幀上方，還會形成一個B的調用幀。等到B運行結束，將結果返回到A，B的調用幀才會銷毀。此時如果函數B內部還調用函數C，那就還有一個C的調用幀，以此類推。例如遞歸操作，一個調用棧中如果保存了大量的棧幀，調用棧非常長，消耗了巨大的內存，會導致爆棧（棧溢出，stack overflow）。**后入先出**的結構。 ![](https://img.kancloud.cn/25/a3/25a338d40657a3a7b06787d18c090098_555x288.png) 當函數內部調用函數時，會在棧頂壓入一個調用幀，該函數執行完后，彈出棧，接著再執行棧頂的調用幀。 尾調用之所以與其他調用不同，就在于它的特殊的調用位置。 那么現在，我們使用尾調用的話，將函數B放到了函數A的最后一步調用，**內層函數不引用外層函數的變量**，就不用保留外層變量的調用幀了。這樣的話內層函數的調用幀，會直接取代外層函數的調用幀。調用棧的長度就會小很多。 當然，如果內層函數B使用了外層函數A的變量，那么就仍然需要保留函數A的棧幀，典型例子即是閉包。 ~~~jsx function f() { let m = 1; let n = 2; return g(m + n); } f(); ~~~ 這應當是一次尾調用。因為m+n的值是通過參數傳入函數g內部，并沒有直接引用，因此也不能說保存 f 內部的變量的值。 下面這種情況內層函數會引用外層函數的值，所以當執行到內層函數時外層函數的調用幀還會存在與當前調用棧中。 ~~~jsx function f() { let m = 1; let n = 2; return function() { return m+n; }; } f(); ~~~ 總得來說，如果所有函數的調用都是尾調用，即只保留內層函數的調用幀，做到每次執行時（例如遞歸操作），一個調用棧中調用幀只有一項，那么調用棧的長度就會小很多，這樣需要占用的內存也會大大減少。這就是尾調用優化的含義。 # 什么時候會開啟尾調用優化在ES5中，尾調用和其他形式的函數調用一樣：腳本引擎創建一個新的函數棧幀并且壓在當前調用的函數的棧幀上面。也就是說，在整個函數棧上，每一個函數棧幀都會被保存，這有可能造成調用棧占用內存過大甚至溢出。 在ES6中，strict模式下，滿足以下條件，尾調用優化會開啟，此時引擎不會創建一個新的棧幀，而是清除當前棧幀的數據并復用： * 尾調用函數不需要訪問當前棧幀中的變量； * 尾調用返回后，函數沒有語句需要繼續執行； * 尾調用的結果就是函數的返回值； ES6的尾調用優化只在嚴格模式下開啟，正常模式是無效的。這是因為在正常模式下，函數內部有兩個變量，可以跟蹤函數的調用棧。 > arguments：返回調用時函數的參數。 > func.caller：返回調用當前函數的那個函數。 尾調用優化發生時，函數的調用棧會改寫，因此上面兩個變量就會失真。嚴格模式禁用這兩個變量，所以尾調用模式僅在嚴格模式下生效。 # 尾遞歸函數調用自身，稱為遞歸。如果尾調用自身，就稱為尾遞歸。 遞歸非常耗費內存，因為需要同時保存成千上百個調用幀，很容易發生"棧溢出"錯誤（stack overflow）。但對于尾遞歸來說，由于只存在一個調用幀，所以永遠不會發生"棧溢出"錯誤。 由此可見，"尾調用優化"對遞歸操作意義重大。 # 遞歸函數的改寫尾遞歸的實現，往往需要改寫遞歸函數，確保最后一步只調用自身。做到這一點的方法，就是把所有用到的內部變量改寫成函數的參數。 例如實現 fibonacci 函數需要用到兩個中間變量 current 和 next，那就把這個中間變量改寫成函數的參數。 ~~~jsx // 實現階乘復雜度 O(n) function factorial(n) { if (n === 1) return 1; return n * factorial(n - 1); } // 尾遞歸只保留一個調用幀，復雜度 O(1) function factorial(n, total = 1) { if (n === 1) return total; console.log(`${n}*${total}`,n*total); return factorial(n - 1, n * total); } ~~~ # 問題 * 在V8引擎層面消除尾遞歸是一個隱式的行為，程序員寫代碼時可能意識不到自己寫了死循環的尾遞歸，而出現死循環后又不會報出stack overflow的錯誤，難以辨別。 * 堆棧信息會在優化的過程中丟失，開發者調試非常困難。 # 參考資料 [js 實現斐波那契數列(數組緩存、動態規劃、尾調用優化)](https://www.jianshu.com/p/bbc7e54a98d6)