1 前言
編程題：輸入一個整數n，輸出斐波那契數列的第n項
有些面試官喜歡問這道題，可能你覺得這太簡單了，用遞回或遞推一下子就實作了，
正當你信心滿滿用了兩種方式實作的時候...
面試官：現在請用“尾遞回”優化你的遞回實作，用“ES6解構賦值”優化你的遞推實作
...
這時候如果你的基本功不扎實，可能你就懵了，
就是這么簡單的一道題，包含著相當多的JS知識點，尤其是它的優化程序可以看出你的基本功扎不扎實，所以有些面試官喜歡問這道題，
下面我們來看遞回和遞推這兩種實作以及它們各自的優化程序
2 遞回和尾遞回
2.1 遞回實作
先來看遞回實作：
function fibonacci(n) {
if (n === 0 || n === 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
來看看這段代碼有什么問題
第一個問題很容易看出來，就是當n非常大的時候，遞回深度過大導致堆疊記憶體溢位，即“爆堆疊”
第二個問題就是有相當多的重復計算，比如：
fibonacci(7)
= fibonacci(6) + fibonacci(5) // 這里計算了f(5)，下面又計算了一次f(5)
= (fibonacci(5) + fibonacci(4)) + (fibonacci(4) + fibonacci(3)) // 這里計算了兩次f(5)
...
2.2 尾呼叫
在解決上面兩個問題之前，先來了解一下什么是尾呼叫
尾呼叫：一個函式里的最后一個動作是回傳一個函式的呼叫結果，即最后一步新呼叫的回傳值被當前函式回傳
比如：
function f(x) {
return g(x)
}
下面這些情況不屬于尾呼叫：
function f(x) {
return g(x) + 1 // 先執行g(x)，最后回傳g(x)的回傳值+1
}
function f(x) {
let ret = g(x) // 先執行了g(x)
return ret // 最后回傳g(x)的回傳值
}
2.3 尾呼叫消除（尾呼叫優化）
一個函式呼叫時，JS引擎會創建一個新的堆疊幀并將其推入呼叫堆疊頂部，用于表示該次函式呼叫
當一個函式呼叫發生時，計算機必須“記住”呼叫函式的位置——回傳位置，才可以在呼叫結束時帶著回傳值回到該位置，回傳位置一般保存在呼叫堆疊上，
在尾呼叫這種特殊情形中，計算機理論上可以不需要記住尾呼叫的位置，而從被呼叫的函式直接帶著回傳值回傳當前函式的回傳位置（相當于直接連續回傳兩次）
如下圖：由于尾呼叫，理論上可以不記住位置2，而從函式g直接帶著回傳值回傳到位置1（即函式f的回傳位置）
由于尾呼叫之前的作業已經完成了，所以當前函式幀（即呼叫時創建的堆疊幀）上包含區域變數等等大部分的東西都不需要了，當前的函式幀經過適當的變動以后可以直接當做尾呼叫的函式的幀使用，然后程式就可以跳到被尾呼叫的函式，
用上圖中的例子來解釋就是，函式f尾呼叫函式g 之前的作業已經完成了，所以呼叫函式f時創建的函式幀直接給函式g用了，就不需要重新給函式g創建堆疊幀，
這種函式幀變動重復使用的程序就叫做尾呼叫消除或尾呼叫優化
2.4 尾遞回
如果函式在尾呼叫位置呼叫自身，則稱這種情況為尾遞回，尾遞回是一種特殊的尾呼叫，即在尾部直接呼叫自身的遞回函式
由于尾呼叫消除，使得尾遞回只存在一個堆疊幀，所以永遠不會“爆堆疊”，
ES6規定了所有ECMAScript的實作都必須部署“尾呼叫消除”，因此在ES6中只要使用尾遞回，就不會發生堆疊溢位
2.5 尾遞回優化斐波那契函式
回到2.1中斐波那契函式存在的兩個問題，可以使用尾遞回來解決“爆堆疊”的問題
需要注意的是：ES6的尾呼叫消除只在嚴格模式下開啟
為了讓原來的遞回函式變成尾遞回，需要改寫函式，讓函式最后一步呼叫自身
// 原遞回函式
function fibonacci(n) {
if (n === 0 || n === 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
// 修改后
'use strict'
function fibonacci(n, pre, cur) {
if (n === 0) {
return n;
}
if (n === 1) {
return cur;
}
return fibonacci(n - 1, cur, pre + cur);
}
// 呼叫
fibonacci(6, 0, 1)
修改后的計算邏輯是這樣的：
f(6, 0, 1)
= f(5, 1, 0 + 1)
= f(4, 1, 1 + 1)
= f(3, 2, 1 + 2)
= f(2, 3, 2 + 3)
= f(1, 5, 3 + 5)
= 8
你可能已經發現了，事實上這就是遞推，從0 + 1開始計算，一直到第n項
另外，可以使用ES6的默認引數來讓函式只傳入一個引數n即可
'use strict'
function fibonacci(n, pre = 0, cur = 1) {
if (n === 0) {
return n;
}
if (n === 1) {
return cur;
}
return fibonacci(n - 1, cur, pre + cur);
}
fibonacci(6)
此外，由于函式改成了尾遞回的形式，第f(n)只與f(n-1)有關，大量重復計算的問題也得到了解決
3 遞推
遞推實作
function fibonacci(n) {
let cur = 0;
let next = 1;
for (let i = 0; i < n; i++) {
let temp = cur;
cur = next;
next += temp;
}
return cur;
}
遞推在性能上沒啥好優化的，但是我們可以在形式上進行優化
利用ES6的解構賦值可以省去中間變數
function fibonacci(n) {
let cur = 0;
let next = 1;
for (let i = 0; i < n; i++) {
[cur, next] = [next, cur + next]
}
return cur;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/347282.html
標籤：JavaScript
上一篇：HTML基礎