App下載

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

猿友 2020-09-30 17:17:05 瀏覽數(shù) (2845)
反饋

文章來源于公眾號:前端UpUp ,作者:TianTianUp

前言

經(jīng)??吹疥P(guān)于尾遞歸這三個詞,遞歸很多時候,都離不開我們,廢話不多說,這次我們梳理一遍關(guān)于遞歸那些事。

在這里關(guān)于遞歸,這里就不贅述了,有興趣的可以去查一查資料。

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

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

尾調(diào)用

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

舉個例子

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

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

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

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

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

  • 效率低,占內(nèi)存。
  • 如果遞歸鏈過長,可能會stack overflow

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

按照阮一峰老師在es6的函數(shù)擴展中的解釋就是:函數(shù)調(diào)用會在內(nèi)存形成一個“調(diào)用記錄”,又稱“調(diào)用幀”(call frame),保存調(diào)用位置和內(nèi)部變量等信息。如果在函數(shù)A的內(nèi)部調(diào)用函數(shù)B,那么在A的調(diào)用幀上方,還會形成一個B的調(diào)用幀。等到B運行結(jié)束,將結(jié)果返回到AB的調(diào)用幀才會消失。如果函數(shù)B內(nèi)部還調(diào)用函數(shù)C,那就還有一個C的調(diào)用幀,以此類推。所有的調(diào)用幀,就形成一個“調(diào)用?!保╟all stack)。

這里的“調(diào)用幀”和“調(diào)用?!?,說的應(yīng)該就是“執(zhí)行環(huán)境”和“調(diào)用棧”。因為尾調(diào)用時函數(shù)的最后一部操作,所以不再需要保留外層的調(diào)用幀,而是直接取代外層的調(diào)用幀,所以可以起到一個優(yōu)化的作用。

從上述的描述中,我們視乎可以理解成

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

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

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

手動優(yōu)化

既然我們知道了,很多瀏覽器對于尾遞歸的優(yōu)化支持的瀏覽器并不多,那你會好奇,當(dāng)我們使用尾遞歸進行優(yōu)化的時候,依然出現(xiàn)棧溢出的錯誤,那么我們?nèi)绾谓鉀Q呢?

我在網(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

0 人點贊