尾調用

1. 定義

尾調用是函數式編程中一個很重要的概念，當一個函數執行時的最后一個步驟是返回另一個函數的調用，這就叫做尾調用。

注意這里函數的調用方式是無所謂的，以下方式均可：

函數調用: func(···)

方法調用: obj.method(···)

call調用: func.call(···)

apply調用: func.apply(···)

并且只有下列表達式會包含尾調用：

條件操作符: ? :

邏輯或: ||

邏輯與: &&

逗號: ,

依次舉例：

const a = x => x ? f() : g();

// f() 和 g() 都在尾部。

const a = () => f() || g();

// g()有可能是尾調用，f()不是

// 因為上述寫法和下面的寫法等效：

const a = () => {

const fResult = f(); // not a tail call

if (fResult) {

return fResult;

} else {

return g(); // tail call

}

}

// 只有當f()的結果為falsey的時候，g()才是尾調用

const a = () => f() && g();

// g()有可能是尾調用，f()不是

// 因為上述寫法和下面的寫法等效：

const a = () => {

const fResult = f(); // not a tail call

if (fResult) {

return g(); // tail call

} else {

return fResult;

}

}

// 只有當f()的結果為truthy的時候，g()才是尾調用

const a = () => (f() , g());

// g()是尾調用

// 因為上述寫法和下面的寫法等效：

const a = () => {

f();

return g();

}

2. 尾調用優化

函數在調用的時候會在調用棧(call stack)中存有記錄，每一條記錄叫做一個調用幀(call frame)，每調用一個函數，就向棧中push一條記錄，函數執行結束后依次向外彈出，直到清空調用棧，參考下圖：

function foo () { console.log(111); }

function bar () { foo(); }

function baz () { bar(); }

baz();

造成這種結果是因為每個函數在調用另一個函數的時候，并沒有 return 該調用，所以JS引擎會認為你還沒有執行完，會保留你的調用幀。

baz() 里面調用了 bar() 函數，并沒有 return 該調用，所以在調用棧中保持自己的調用幀，同時 bar() 函數的調用幀在調用棧中生成，同理，bar() 函數又調用了 foo() 函數，最后執行到 foo() 函數的時候，沒有再調用其他函數，這里沒有顯示聲明 return，所以這里默認 return undefined。

foo() 執行完了，銷毀調用棧中自己的記錄，依次銷毀 bar() 和 baz() 的調用幀，最后完成整個流程。

如果對上面的例子做如下修改：

function foo () { console.log(111); }

function bar () { return foo(); }

function baz () { return bar(); }

baz();

這里要注意：尾調用優化只在嚴格模式下有效。

在非嚴格模式下，大多數引擎會包含下面兩個屬性，以便開發者檢查調用棧：

• func.arguments: 表示對 func最近一次調用所包含的參數

• func.caller: 引用對 func最近一次調用的那個函數

在尾調用優化中，這些屬性不再有用，因為相關的信息可能以及被移除了。因此，嚴格模式(strict mode)禁止這些屬性，并且尾調用優化只在嚴格模式下有效。

如果尾調用優化生效，流程圖就會變成這樣：

我們可以很清楚的看到，尾調用由于是函數的最后一步操作，所以不需要保留外層函數的調用記錄，只要直接用內層函數的調用記錄取代外層函數的調用記錄就可以了，調用棧中始終只保持了一條調用幀。

這就叫做尾調用優化，如果所有的函數都是尾調用的話，那么在調用棧中的調用幀始終只有一條，這樣會節省很大一部分的內存，這也是尾調用優化的意義。

尾遞歸

1. 定義

先來看一下遞歸，當一個函數調用自身，就叫做遞歸。

function foo () {

foo();

}

上面這個操作就叫做遞歸，但是注意了，這里沒有結束條件，是死遞歸，所以會報棧溢出錯誤的，寫代碼時千萬注意給遞歸添加結束條件。

那么什么是尾遞歸？前面我們知道了尾調用的概念，當一個函數尾調用自身，就叫做尾遞歸。

function foo () {

return foo();

}

2. 作用

那么尾遞歸相比遞歸而言，有哪些不同呢？我們通過下面這個求階乘的例子來看一下：

function factorial (num) {

if (num === 1) return 1;

return num * factorial(num - 1);

}

factorial(5); // 120

factorial(10); // 3628800

factorial(500000); // Uncaught RangeError: Maximum call stack size exceeded

上面是使用遞歸來計算階乘的例子，操作系統為JS引擎調用棧分配的內存是有大小限制的，如果計算的數字足夠大，超出了內存最大范圍，就會出現棧溢出錯誤。

這里500000并不是臨界值，只是我用了一個足夠造成棧溢出的數。

如果用尾遞歸來計算階乘呢？

'use strict';

function factorial (num, total) {

if (num === 1) return total;

return factorial(num - 1, num * total);

}

factorial(5, 1); // 120

factorial(10, 1); // 3628800

factorial(500000, 1); // 分情況

// 注意，雖然說這里啟用了嚴格模式，但是經測試，在Chrome和Firefox下，還是會報棧溢出錯誤，并沒有進行尾調用優化

// Safari瀏覽器進行了尾調用優化，factorial(500000, 1)結果為Infinity，因為結果超出了JS可表示的數字范圍

// 如果在node v6版本下執行，需要加--harmony_tailcalls參數，node --harmony_tailcalls test.js

// node最新版本已經移除了--harmony_tailcalls功能

通過尾遞歸，我們把復雜度從O(n)降低到了O(1)，如果數據足夠大的話，會節省很多的計算時間。由此可見，尾調用優化對遞歸操作意義重大，所以一些函數式編程語言將其寫入了語言規格。

避免改寫遞歸函數

尾遞歸的實現，往往需要改寫遞歸函數，確保最后一步只調用自身。要做到這一點，需要把函數內部所有用到的中間變量改寫為函數的參數，就像上面的factorial()函數改寫一樣。

這樣做的缺點就是語義不明顯，要計算階乘的函數，為什么還要另外傳入一個參數叫total？解決這個問題的辦法有兩個：

1. ES6參數默認值

'use strict';

function factorial (num, total = 1) {

if (num === 1) return total;

return factorial(num - 1, num * total);

}

factorial(5); // 120

factorial(10); // 3628800

2. 用一個符合語義的函數去調用改寫后的尾遞歸函數

function tailFactorial (num, total) {

if (num === 1) return total;

return tailFactorial(num - 1, num * total);

}

function factorial (num) {

return tailFactorial(num, 1);

}

factorial(5); // 120

factorial(10); // 3628800

上面這種寫法其實有點類似于做了一個函數柯里化，但不完全符合柯里化的概念。函數柯里化是指把接受多個參數的函數轉換為接受一個單一參數(最初函數的第一個參數)的函數，并且返回接受余下參數且返回結果的新函數。

概念看著很繞口，我們來個例子感受一下：

// 普通加法函數

function add (x, y, z) {

return x + y + z;

}

add(1, 2, 3); // 6

// 改寫為柯里化加法函數

function add (x) {

return function (y) {

return function (z) {

return x + y + z;

}

}

}

add(1)(2)(3); // 6

可以看到，柯里化函數通過閉包找到父作用域里的變量，最后依次相加輸出結果。通過這個例子，可能看不出為什么要用柯里化，有什么好處，這個我們以后再談，這里先引出一個概念。

是把接受多個參數的函數變換成接受一個單一參數(最初函數的第一個參數)的函數，并且返回接受余下的參數且返回結果的新函數的技術。

如果用柯里化改寫求階乘的例子：

// 柯里化函數

function curry (fn) {

var _fnArgLength = fn.length;

function wrap (...args) {

var _args = args;

var _argLength = _args.length;

// 如果傳的是所有參數，直接返回fn調用

if (_fnArgLength === _argLength) {

return fn.apply(null, args);

}

function act (...args) {

_args = _args.concat(args);

if (_args.length === _fnArgLength) {

return fn.apply(null, _args);

}

return act;

}

return act;

}

return wrap;

}

// 尾遞歸函數

function tailFactorial (num, total) {

if (num === 1) return total;

return tailFactorial(num - 1, num * total);

}

// 改寫

var factorial = curry(tailFactorial);

factorial(5)(1); // 120

factorial(10)(1); // 3628800

這是符合柯里化概念的寫法，在阮一峰老師的文章中是這樣寫的：

function currying(fn, n) {

return function (m) {

return fn.call(this, m, n);

};

}

function tailFactorial(n, total) {

if (n === 1) return total;

return tailFactorial(n - 1, n * total);

}

const factorial = currying(tailFactorial, 1);

factorial(5) // 120

我個人認為，這種寫法其實不是柯里化，因為并沒有將多參數的tailFacrotial改寫為接受單參數的形式，只是換了一種寫法，和下面這樣寫意義是一樣的：

function factorial (num) {

return tailFactorial(num, 1);

}

function tailFactorial (num, total) {

if (num === 1) return total;

return tailFactorial(num - 1, num * total);

}

factorial(5); // 120

factorial(10); // 3628800

結束

這篇文章我們主要討論了尾調用優化和柯里化。要注意的是，經過測試，Chrome和Firefox并沒有對尾調用進行優化，Safari對尾調用進行了優化。Node高版本也已經去除了通過--harmony_tailcalls參數啟用尾調用優化。

有任何問題，歡迎大家留言討論，另附我的博客網站，快來呀~~

歡迎關注我的公眾號

參考鏈接

http://www.ruanyifeng.com/blog/2015/04/tail-call.html https://juejin.im/post/6844903544756125704 https://github.com/lamdu/lamdu/issues/90