尾調(diào)用

1. 定義

尾調(diào)用是函數(shù)式編程中一個很重要的概念接箫，當(dāng)一個函數(shù)執(zhí)行時的最后一個步驟是返回另一個函數(shù)的調(diào)用，這就叫做尾調(diào)用朵诫。

注意這里函數(shù)的調(diào)用方式是無所謂的列牺，以下方式均可：

函數(shù)調(diào)用:     func(···)
方法調(diào)用:     obj.method(···)
call調(diào)用:     func.call(···)
apply調(diào)用:    func.apply(···)

并且只有下列表達式會包含尾調(diào)用：

條件操作符:      ? :
邏輯或:         ||
邏輯與:         &&
逗號:           ,

依次舉例：

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

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

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

// g()有可能是尾調(diào)用拗窃，f()不是

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

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

// 只有當(dāng)f()的結(jié)果為falsey的時候瞎领，g()才是尾調(diào)用

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

// g()有可能是尾調(diào)用泌辫，f()不是

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

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

// 只有當(dāng)f()的結(jié)果為truthy的時候，g()才是尾調(diào)用

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

// g()是尾調(diào)用

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

const a = () => {
    f();
    return g();
}

2. 尾調(diào)用優(yōu)化

函數(shù)在調(diào)用的時候會在調(diào)用棧（call stack）中存有記錄九默，每一條記錄叫做一個調(diào)用幀（call frame）震放，每調(diào)用一個函數(shù)，就向棧中push一條記錄驼修，函數(shù)執(zhí)行結(jié)束后依次向外彈出殿遂，直到清空調(diào)用棧，參考下圖：

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

baz();

call stack

造成這種結(jié)果是因為每個函數(shù)在調(diào)用另一個函數(shù)的時候乙各，并沒有 return 該調(diào)用墨礁，所以JS引擎會認為你還沒有執(zhí)行完，會保留你的調(diào)用幀耳峦。

baz() 里面調(diào)用了 bar() 函數(shù)恩静，并沒有 return 該調(diào)用，所以在調(diào)用棧中保持自己的調(diào)用幀蹲坷，同時 bar() 函數(shù)的調(diào)用幀在調(diào)用棧中生成驶乾，同理，bar() 函數(shù)又調(diào)用了 foo() 函數(shù)循签，最后執(zhí)行到 foo() 函數(shù)的時候级乐，沒有再調(diào)用其他函數(shù)，這里沒有顯示聲明 return县匠，所以這里默認 return undefined风科。

foo() 執(zhí)行完了，銷毀調(diào)用棧中自己的記錄乞旦，依次銷毀 bar() 和 baz() 的調(diào)用幀贼穆，最后完成整個流程。

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

function foo () { console.log(111); }
function bar () { return foo(); }
function baz () { return bar(); }

baz();

這里要注意：尾調(diào)用優(yōu)化只在嚴格模式下有效杆查。

在非嚴格模式下，大多數(shù)引擎會包含下面兩個屬性臀蛛，以便開發(fā)者檢查調(diào)用棧：

• func.arguments: 表示對 func最近一次調(diào)用所包含的參數(shù)
• func.caller: 引用對 func最近一次調(diào)用的那個函數(shù)

在尾調(diào)用優(yōu)化中亲桦，這些屬性不再有用，因為相關(guān)的信息可能以及被移除了浊仆。因此客峭，嚴格模式(strict mode)禁止這些屬性，并且尾調(diào)用優(yōu)化只在嚴格模式下有效抡柿。

如果尾調(diào)用優(yōu)化生效蒋得，流程圖就會變成這樣：

call stack

我們可以很清楚的看到墙歪，尾調(diào)用由于是函數(shù)的最后一步操作，所以不需要保留外層函數(shù)的調(diào)用記錄唐片，只要直接用內(nèi)層函數(shù)的調(diào)用記錄取代外層函數(shù)的調(diào)用記錄就可以了，調(diào)用棧中始終只保持了一條調(diào)用幀何暇。

這就叫做尾調(diào)用優(yōu)化，如果所有的函數(shù)都是尾調(diào)用的話，那么在調(diào)用棧中的調(diào)用幀始終只有一條二跋，這樣會節(jié)省很大一部分的內(nèi)存，這也是尾調(diào)用優(yōu)化的意義流昏。

尾遞歸

1. 定義

先來看一下遞歸扎即，當(dāng)一個函數(shù)調(diào)用自身，就叫做遞歸况凉。

function foo () {
    foo();
}

上面這個操作就叫做遞歸谚鄙，但是注意了，這里沒有結(jié)束條件刁绒，是死遞歸闷营，所以會報棧溢出錯誤的，寫代碼時千萬注意給遞歸添加結(jié)束條件膛锭。

那么什么是尾遞歸粮坞？
前面我們知道了尾調(diào)用的概念，當(dāng)一個函數(shù)尾調(diào)用自身初狰，就叫做尾遞歸莫杈。

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

上面是使用遞歸來計算階乘的例子筝闹，操作系統(tǒng)為JS引擎調(diào)用棧分配的內(nèi)存是有大小限制的，如果計算的數(shù)字足夠大腥光，超出了內(nèi)存最大范圍关顷，就會出現(xiàn)棧溢出錯誤。

這里500000并不是臨界值武福，只是我用了一個足夠造成棧溢出的數(shù)议双。

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

'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);           // 分情況

// 注意捉片，雖然說這里啟用了嚴格模式平痰，但是經(jīng)測試，在Chrome和Firefox下伍纫，還是會報棧溢出錯誤宗雇，并沒有進行尾調(diào)用優(yōu)化
// Safari瀏覽器進行了尾調(diào)用優(yōu)化，factorial(500000, 1)結(jié)果為Infinity莹规，因為結(jié)果超出了JS可表示的數(shù)字范圍
// 如果在node v6版本下執(zhí)行赔蒲，需要加--harmony_tailcalls參數(shù)，node --harmony_tailcalls test.js
// node最新版本已經(jīng)移除了--harmony_tailcalls功能

通過尾遞歸，我們把復(fù)雜度從O(n)降低到了O(1)舞虱，如果數(shù)據(jù)足夠大的話欢际，會節(jié)省很多的計算時間。
由此可見砾嫉，尾調(diào)用優(yōu)化對遞歸操作意義重大幼苛，所以一些函數(shù)式編程語言將其寫入了語言規(guī)格。

避免改寫遞歸函數(shù)

尾遞歸的實現(xiàn)焕刮，往往需要改寫遞歸函數(shù)舶沿，確保最后一步只調(diào)用自身。
要做到這一點配并，需要把函數(shù)內(nèi)部所有用到的中間變量改寫為函數(shù)的參數(shù)括荡，就像上面的factorial()函數(shù)改寫一樣。

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

1. ES6參數(shù)默認值

'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. 用一個符合語義的函數(shù)去調(diào)用改寫后的尾遞歸函數(shù)

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

上面這種寫法其實有點類似于做了一個函數(shù)柯里化观腊，但不完全符合柯里化的概念邑闲。
函數(shù)柯里化是指把接受多個參數(shù)的函數(shù)轉(zhuǎn)換為接受一個單一參數(shù)（最初函數(shù)的第一個參數(shù)）的函數(shù)，并且返回接受余下參數(shù)且返回結(jié)果的新函數(shù)梧油。

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

// 普通加法函數(shù)
function add (x, y, z) {
    return x + y + z;
}

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

// 改寫為柯里化加法函數(shù)
function add (x) {
    return function (y) {
        return function (z) {
            return x + y + z;
        }
    }
}

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

可以看到，柯里化函數(shù)通過閉包找到父作用域里的變量儡陨，最后依次相加輸出結(jié)果褪子。
通過這個例子，可能看不出為什么要用柯里化骗村，有什么好處嫌褪，這個我們以后再談，這里先引出一個概念胚股。

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

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

// 柯里化函數(shù)
function curry (fn) {
    var _fnArgLength = fn.length;

    function wrap (...args) {
        var _args = args;
        var _argLength = _args.length;
        // 如果傳的是所有參數(shù)琅拌，直接返回fn調(diào)用
        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;
}

// 尾遞歸函數(shù)
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

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

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

結(jié)束

這篇文章我們主要討論了尾調(diào)用優(yōu)化和柯里化即彪。
要注意的是，經(jīng)過測試，Chrome和Firefox并沒有對尾調(diào)用進行優(yōu)化隶校，Safari對尾調(diào)用進行了優(yōu)化漏益。
Node高版本也已經(jīng)去除了通過--harmony_tailcalls參數(shù)啟用尾調(diào)用優(yōu)化。

有任何問題深胳，歡迎大家留言討論绰疤，另附我的博客網(wǎng)站，快來呀~~

參考鏈接

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