[[344640]]

 前言

在這里關于遞歸，這里就不贅述了，有興趣的可以去查一查資料。

需要了解如何優(yōu)化尾遞歸的話，我們需要從最開始講起。

• 什么是尾調用
• 什么是尾遞歸
• 如何優(yōu)化尾遞歸

尾調用
從字面理解，自然而言就是在函數(shù)的尾部返回一個函數(shù)的調用，通常來說，指的是函數(shù)執(zhí)行的最后一步。

舉個例子👇

const fn = () => f1() || f2() 
// 這里的話, f2函數(shù)有可能是尾調用,f1不可能是尾調用 

為什么f1函數(shù)不是呢，我們看這個函數(shù)的等價形式👇

const fn = function () { 
    const flag = f1() 
    if(flag) { 
        return flag 
    } else { 
        return f2() 
    } 
} 

似乎寫到這里，根據(jù)尾調用定義，我們就明白了，只有f2函數(shù)是在尾部調用。

說到這里，為什么要說尾調用呢?我們事先想一想傳統(tǒng)的遞歸，典型的就是首先執(zhí)行遞歸調用，然后根據(jù)這個遞歸的返回值并結算結果，那么傳統(tǒng)的遞歸缺點有哪些呢👇

• 效率低，占內存。
• 如果遞歸鏈過長，可能會stack overflow

那么我們是不是可以做優(yōu)化呢，這就可以涉及上面提到的尾調用，它的原理是啥呢👇

“按照阮一峰老師在es6的函數(shù)擴展中的解釋就是：函數(shù)調用會在內存形成一個“調用記錄”，又稱“調用幀”（call frame），保存調用位置和內部變量等信息。如果在函數(shù)A的內部調用函數(shù)B，那么在A的調用幀上方，還會形成一個B的調用幀。等到B運行結束，將結果返回到A，B的調用幀才會消失。如果函數(shù)B內部還調用函數(shù)C，那就還有一個C的調用幀，以此類推。所有的調用幀，就形成一個“調用棧”（call stack）。
“這里的“調用幀”和“調用棧”，說的應該就是“執(zhí)行環(huán)境”和“調用棧”。因為尾調用時函數(shù)的最后一部操作，所以不再需要保留外層的調用幀，而是直接取代外層的調用幀，所以可以起到一個優(yōu)化的作用。
從上述的描述中，我們視乎可以理解成

• 它的原理類似于當編譯器檢測到一個函數(shù)調用是尾遞歸時，它會覆蓋當前的活動記錄而不是在函數(shù)棧中創(chuàng)建一個新的調用記錄。
• 這樣子，我們也可以理解成，不同的語言編譯器或者是解釋器做了尾遞歸優(yōu)化，才讓它不會爆棧。

既然是這樣子的話，尾遞歸的優(yōu)化，取決于瀏覽器，那具體有哪些主流瀏覽器支持呢👇

safari 和火狐，有興趣的可以去了解一下，可以寫個斐波那契數(shù)列數(shù)列驗證一下。

手動優(yōu)化
既然我們知道了，很多瀏覽器對于尾遞歸的優(yōu)化支持的瀏覽器并不多，那你會好奇，當我們使用尾遞歸進行優(yōu)化的時候，依然出現(xiàn)棧溢出的錯誤，那么我們如何解決呢？👇

我在網(wǎng)上看到一個不錯的方案，采用的是蹦床函數(shù)👇

function trampoline(f) { 
  while (f && f instanceof Function) { 
    f = f(); 
  } 
  return f; 
} 

那么如何使用呢👇

我們拿最常見的斐波那契數(shù)列來說吧

function fibonacci(n) { 
  if (n === 0) return 0 
  if (n === 1) return 1 
  return fibonacci(n - 1) + fibonacci(n - 2) 
} 

根據(jù)上面的式子，我們可以將其寫成迭代形式，用一個變量去緩存它的值👇

function fibonacci (n, ac1 = 0, ac2 = 1) { 
    return n <= 1 ? ac2 :fibonacci(n - 1, ac2, ac1 + ac2); 
} 

其實試過的小伙伴，會發(fā)現(xiàn)，當你需要求的n足夠大的時候，還是會報錯，類似于下面的錯誤信息👇

// fibonacci(10000) 
Uncaught RangeError: Maximum call stack size exceeded 

這個時候，那么我們如何去優(yōu)化呢？難道真的沒有辦法可以解決了嗎👇

這里得借鑒下別人的思路，我覺得挺不錯的，這里就給出代碼👇

function trampoline(f) { 
  while (f && f instanceof Function) { 
    f = f(); 
  } 
  return f; 
} 

你可以把這個函數(shù)稱之為蹦床函數(shù), 這個函數(shù)的作用就是放回一個新的函數(shù)，我們將它們倆結合起來的話，棧溢出的問題似乎就可以解決了👇

// 可以試一試噢 
trampoline(fibonacci (10000)) 

這里的蹦床函數(shù)，我是參考別人的寫法，似乎這樣子寫的話，不太行，我個人覺得這樣子可以避免調用棧溢出，實際情況下，這樣子是行不通的，哪里有行不通的，還望指出。

當然了，手動優(yōu)化，可以將遞歸的過程改寫成迭代的過程，就拿斐波那契數(shù)列這題來說，我們可以使用動態(tài)規(guī)劃來完成👇，O（n）完成答案的更新。

// 偽代碼 
F[i] = F[i-1] + F[i-2] 

嗯，將一個尾遞歸函數(shù)轉換成循環(huán)迭代函數(shù)，算是手動優(yōu)化一種方式，在我們語言沒有原生支持尾遞歸優(yōu)化，那么可以考慮這種情況。

對于尾遞歸而言，我們需要了解優(yōu)化它的原理，如果有必要的話，將遞歸的形式寫成迭代的形式，通過迭代方式，降低重復值的計算，當然了，這個過程，有時候是比較難的，值得我們去思考。