??

尾調用及遞歸優化

ES6 規范中添加了對尾調用優化的支持,雖然目前來看支持情況還不是很好,但了解其原理還是很有必要的,有助于我們編寫高效的代碼,一旦哪天引擎支持該優化了,將會收獲性能上的提升。

討論尾調用前,先看函數正常調用時其形成的堆棧(stack frame)情況。

函數的調用及調用堆棧

先看一個概念:調用堆棧(call stack),或叫調用?。╯tack frame)。

我理解的調用堆棧:因為函數調用后,流程會進入到被調用函數體,此時需要傳入一些入參,這些入參需要存放到一個位置,另外當函數調用結束后,執行流程需要返回到被調用的地方,這個返回的地方也需要被記錄下來。所以會為這次函數調用分配一個存儲區域,存放調用時傳入的入參,調用結束后返回的地址。這個存儲區域保存的都是跟本次函數調用相關的數據,所以,它是該函數的調用堆棧。

考察下面的示例代碼:

function g(x) {
  return x; // (C)
}
function f(a) {
  let b = a + 1;
  return g(b); // (B)
}
console.log(f(2)); // (A)

下面模擬 JaavScript 引擎在執行上面代碼時的流程,

  • 首先對于全局作用哉來說,存在兩個字面量(不算上全局 window) f,g,所以一開始執行時,已經默認有一個全局的堆棧信息了,看起來大概是這樣子:
+-------------------------------------+
|                                     |
|         f=function(a){...}          |
|         g=function(x){...}          |
|                                     |
+-------------------------------------+
  • 調用 f(2) 并生成調用堆棧,代碼執行流程進入 f 的函數體中。形成了第一個 stack frame,里面有 f(2) 入參 a,函數體中聲明的變量 b 以及被調用的位置 A。此時的堆棧是下面的樣子:
+-------------------------------------+
|                                     |
|         a=2                         |
|         b=2+1                       |
|         Line A                      |
|                                     |
+-------------------------------------+
|                                     |
|         f=function(a){...}          |
|         g=function(x){...}          |
|                                     |
+-------------------------------------+
  • 在函數 f 的函數體中,調用 g 代碼流程進入 g 的函數體,同樣,為其生成相應的調用堆棧,保存入參 x,調用位置 B。
+-------------------------------------+
|                                     |
|         x=3                         |
|         Line B                      |
|                                     |
+-------------------------------------+
|                                     |
|         a=2                         |
|         b=2+1                       |
|         Line A                      |
|                                     |
+-------------------------------------+
|                                     |
|         f=function(a){...}          |
|         g=function(x){...}          |
|                                     |
+-------------------------------------+
  • 函數 greturn 進行返回后,因為 g 已經完成使命,其相關的調用堆棧被銷毀。代碼執行流程回到 g 被調用的地方 A,相當于代碼執行流程回到了 f 函數體中。此時的堆棧是這樣的:
+-------------------------------------+
|                                     |
|         a=2                         |
|         b=2+1                       |
|         Line A                      |
|                                     |
+-------------------------------------+
|                                     |
|         f=function(a){...}          |
|         g=function(x){...}          |
|                                     |
+-------------------------------------+
  • f 函數體中拿到 g 的返回后,什么也沒干,直接 return 返回,此時結束了 f 的執行,流程回到 f 被調用的地方 A,即流程回到全局作用域,銷毀 f 的調用堆棧。此時的堆棧為:
+-------------------------------------+
|                                     |
|         f=function(a){...}          |
|         g=function(x){...}          |
|                                     |
+-------------------------------------+
  • 全局作用域中,得到返回值后將其打印輸出結束了整段代碼。

尾調用

如果一個函數最后一步是調用另一個函數,則這個調用為尾調用。比如:

function g(x) {
  return x;
}
function f(y) {
  var a = y + 1;
  return g(a);
}

但下面這個就不算尾調用了:

function g(x) {
  return x;
}
function f(y) {
  var a = y + 1;
  return g(a) + 1;
}

因為這里 f 中最后一步操作并不是對 g 的調用,在拿到 g 函數的返回后還進行了另外的操作 g(a)+1。其代碼相當于如下的形式:

function g(x) {
  return x;
}
function f(y) {
  var a = y + 1;
  var tmp = g(a);
  var result = tmp + 1;
  return result;
}

經過改造后就能很明顯看出,其中對 g 的調用不是尾調用了。

尾調用的判定

函數的調用形式

首先,JavaScript 中調用函數是多樣的,只要這是另一函數中最后一步操作,都可稱作尾調用。比如以下的函數調用形式:

  • 正常函數調用:fn(...)
  • 訪問對象屬性并調用:obj.method(...)
  • 通過 Function.prototype.all 調用:fn.call(...)
  • 通過 apply 調用:fn.apply(...)

表達式中的尾調用

因為剪頭函數的函數體可以是表達式,所以表達式最終的步驟是什么決定了該剪頭函數中是否包含尾調用。

能夠形成尾調用的表達式有如下這些,

  • 三元表達式:?:
const a = x => x ? f() : g();

其中 f()g() 都是尾調用,表達式最終結果要么是對 f() 的調用,要么是對 g() 的調用。

  • 邏輯或表達式:||
const a = () => f() || g();

上面示例中, f() 不是尾調用,而對 g() 的調用是尾調用。這點可通過下面轉換后的等效代碼看出來:

const a = () => {
    let fResult = f(); // not a tail call
    if (fResult) {
        return fResult;
    } else {
        return g(); // tail call
    }
};

a||b 的意思是如果 a 真則返回 a 的值,否則繼續判定 b,此時無論 b 真假與否,整個表達式的返回都是 b。

所以從上面的轉換中看出,對于 f() 的調用,需要進一步對其返回值進行處理,而不是直接將 f() 進行返回,所以 f() 并不是函數體中最后一步操作,但 g() 是,因為對于 g() 的返回值沒有其他操作,而是直接返回。

  • 邏輯與表達式:&&
const a = () => f() && g();

與邏輯或表達式雷同,這里需要對 f() 的返回值進一步處理,進行判定后決定整個表達式的執行,所以 f() 不是尾調用,而 g() 是。 其等效的代碼如下:

const a = () => {
    let fResult = f(); // not a tail call
    if (!fResult) {
        return fResult;
    } else {
        return g(); // tail call
    }
};
  • 逗號表達式:expression,expression
const a = () => (f() , g());

這個就比較好理解了,逗號表達式是依次執行的,整個表達式返回結果為最后一個表達式。所以這里 f() 不是尾調用,g() 是。

需要注意的是,單獨的函數調用并不是尾調用,比如下面這樣:

function foo() {
    bar(); // this is not a tail call in JS
}

這里 bar() 并不是尾調用,因為函數體中,最后一步操作并不是返回 bar(),而是隱式地返回 undefined。其等效的代碼為:

function foo() {
    bar();
    return undefined;
}

像這種情況其實并不能簡單地通過加一個 return 將其變成尾調用。因為這樣就改變了 foo 的返回值,其功能有可能就變了,調用方就不能再依賴于 foo() 返回的是 undefined。

尾調用優化

回到最開始的那個示例:

function g(x) {
  return x; // (C)
}
function f(a) {
  let b = a + 1;
  return g(b); // (B)
}
console.log(f(2)); // (A)

這里 f(a) 中就包含一個尾調用 g(b)。并且通過前面的調用堆棧的分析,可以知道,每一次函數調用都需要生成相應的調用堆棧,會有存儲的開銷。

如果仔細看前面調用過程的分析,會發現,在 f(a) 函數體中,當我們調用 g(b) 時,就可以將 f(a) 的調用堆棧直接銷毀了,其中 f(a) 相關的內容不會再被用到,除了其中關于 f(a) 被調用位置的記錄。這個位置需要在調用 g(b) 后返回。

所以,完全可以省掉 f(a) 作為中間商這一步,將 f(a) 反返回地址告訴 g(x),這樣 g(x) 在執行完成后直接返回到代碼中 A 標記處。

上面優化后的執行場景下,其調用堆棧的分配則變成了:

  • 調用 f(2),為其分配堆棧
  • 調用 g(b),為其分配堆棧。同時發現 g(b)f(a) 的末尾直接被返回, f(a) 中存儲的變量 b 這些在后續執行中不會再被用到,將 f(a) 的調用規模銷毀。
  • 執行 g(b) 并返回到 A 標記處。

最最開始不同之處在于,在創建 g(b) 的調用堆棧時,同時銷毀了 f(a) 的調用堆棧。這當然是 JavaScript 引擎去實現的。

其好處顯而易見,在函數連續調用過程中,堆棧數沒有增加。假如不止一次尾調用, g(x) 中還存在對另外函數的尾調用,這樣的優化可以持續下去,也就是說,堆棧數并沒有隨著函數調用的增多而增加。

利用這個特性,我們可以將一些不是尾調用的函數想辦法改成尾調用,達到優化調用堆棧的目的,這便是尾調用優化。

尾遞歸調用

如果函數的尾調用是對自己的調用,便形成了遞歸調用,同時還是歸調用,所以合稱 尾遞歸調用。相比于傳統的遞歸,調用堆棧極速增加的不同,尾遞歸調用的調用堆棧是恒定的,這由前面的分析可知。

所以尾調用優化特別適合用于遞歸的情況,收益會很大。

計算階乘就是典型的遞歸場景:

function factorial(x) {
    if (x <= 0) {
        return 1;
    } else {
        return x * factorial(x-1); // (A)
    }
}

但上面這樣的實現并不是尾調用。不過可以通過添加一個額外的方法來達到優化成尾調用的目的。

function factorial(n) {
    return facRec(n, 1);
}
function facRec(x, acc) {
    if (x <= 1) {
        return acc;
    } else {
        return facRec(x-1, x*acc); // (A)
    }
}

此時 facRec 便是一個尾遞歸調用。

其他示例

利用尾遞歸調用實現循環語句。

function forEach(arr, callback, start = 0) {
    if (0 <= start && start < arr.length) {
        callback(arr[start], start, arr);
        return forEach(arr, callback, start+1); // tail call
    }
}
forEach(['a', 'b'], (elem, i) => console.log(`${i}. ${elem}`));

// Output:
// 0. a
// 1. b
function findIndex(arr, predicate, start = 0) {
    if (0 <= start && start < arr.length) {
        if (predicate(arr[start])) {
            return start;
        }
        return findIndex(arr, predicate, start+1); // tail call
    }
}
findIndex(['a', 'b'], x => x === 'b'); // 1

相關資源

posted @ 2019-06-07 09:24 劉哇勇 閱讀(...) 評論(...) 編輯 收藏

Bingo!!

少年,我看你骨骼清奇,怕是一名前端吧?