es6出來(lái)已經(jīng)很長(zhǎng)時(shí)間了湿痢，平時(shí)工作中也會(huì)用到很多es6的新特性咆疗，自以為很多東西已經(jīng)了解清楚了豪椿。

周末有空從頭開始把軟大神寫的es6從頭開始又看了一遍，發(fā)現(xiàn)好多東西都是囫圇吞棗榄笙，很多概念都沒理解清楚。特別是在函數(shù)的擴(kuò)展模塊祷蝌，以前壓根就沒看到最后茅撞，關(guān)于遞歸尾調(diào)用這里，概念都不清楚巨朦。

之前寫的權(quán)限框架涉及很多tree的遞歸遍歷米丘，遞歸消耗性能，遞歸嵌套層級(jí)過多容易導(dǎo)致棧溢出糊啡，這個(gè)問題眾所周知拄查，所以怎么處理遞歸調(diào)用就很重要，這個(gè)尾調(diào)用優(yōu)化正好就是解決這個(gè)問題棚蓄。

關(guān)于尾調(diào)用的概念堕扶，直接引用阮一峰的文檔，也可以直接查看ES6文檔http://es6.ruanyifeng.com/#docs/function

一梭依、階乘

1.遞歸

       const { log } = console
        //獲取階乘
        //方式一：遞歸 復(fù)雜度O(n) 
        function getJc(n){
            if(n===1) return 1
            return n * getJc(n-1)
        }
        log('遞歸',getJc(4))

2.遞歸優(yōu)化

        //方式二：遞歸優(yōu)化 復(fù)雜度O(1)
        function getJc1(n,x){
            if(n===1) return x
            return  getJc1(n-1, x * n)
        }
        log('遞歸優(yōu)化',getJc1(6,1))

3.循環(huán)

        //方式三：循環(huán) 效率高稍算，缺點(diǎn)是定義變量多，變量改變頻繁
        function getJc2(n){
            if( n <= 2 ) return n
            let cj = 1
            let n1 = 1
            for( let i = 1; i <= n; i++ ){
                n1 = cj
                cj = n1 * i
            }
            return cj
        }
        log('循環(huán)',getJc2(6))        

4.柯里化

//這種方式只是將傳參方式改變了下役拴，本質(zhì)還是尾調(diào)用優(yōu)化處理
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ù)列

1.遞歸

// 廣度優(yōu)先遍歷
let tempArr = []
function f(tree){
    tempArr = []
    tree.forEach(item=>{
        console.log(item.id)
        if(item.child){
            tempArr = tempArr.concat(item.child)
        }
    })
    tempArr.length > 0 && f(tempArr)
}
const tree = [{id:1,child:
[{id:2,child:[{id:4,child:[{id:8,id:9}]}]}]}]
f(tree) //1 2 4 9

// 深度優(yōu)先遍歷
let temArr = []
function f(tree){
    tree.forEach(item=>{
        console.log('item.id',item.id)
        if(item.child){
            f(item.child)
        }
    })
}

      const { log } = console
        
      //斐波那契數(shù)列
        //方式一：遞歸
        function Fibonacci (n) {
            if ( n <= 1 ) {return 1};
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
        log('遞歸',Fibonacci(9))

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

        //方式二：尾遞歸調(diào)用優(yōu)化 優(yōu)點(diǎn)：減少重復(fù)計(jì)算，性能高扎狱，代碼優(yōu)雅 
       // 缺點(diǎn)：代碼理解難度大
        function Fibonacci1 (n,x=1,y=1) {
            if ( n <= 1 ) {return y};
            return Fibonacci1(n - 1,y,x+y);
        }
      log('尾調(diào)用優(yōu)化',Fibonacci1(9))

function curr1(fn,x,y){
    return function(n){
        return fn.call(this,n,x,y)
    }
}
const n1 = curr1(Fibonacci1,1,1)
n1(8) // 21
n1(6) // 8

3.循環(huán)

        //方式三：循環(huán) 優(yōu)點(diǎn)：無(wú)重復(fù)計(jì)算侧到，速度快；缺點(diǎn)：變量多淤击，改變頻繁
        function Fibonacci2 (n) {
            if ( n <= 2 ) {return n};
            let n1 = 1,n2 = 1, sum = 0
            for(let i = 2; i <= n; i++){
                sum = n1 + n2
                n1 = n2
                n2 = sum
            }
            return sum;
        }
        log('循環(huán)',Fibonacci2(80))

4.遞歸?緩存

        //方式四：遞歸?緩存 
       
        function memozi(fn){
            let obj = {}
            return function(n){
                if(!obj[n]){
                    return obj[n] = fn(n)
                }else{
                    return obj[n]
                }
            }
        }
        const Fibonacci3 =  memozi ( function(n) {
            if ( n <= 2 ) {return n};
            return Fibonacci3(n-1) + Fibonacci3(n-2);
        })
        log('遞歸?緩存',Fibonacci3(80))

以下匠抗，引用于阮一峰《ECMAScript 6 入門》
http://es6.ruanyifeng.com/#docs/function

一、什么是尾調(diào)用污抬？

尾調(diào)用（Tail Call）是函數(shù)式編程的一個(gè)重要概念汞贸，本身非常簡(jiǎn)單徽惋，一句話就能說清楚叹谁，就是指某個(gè)函數(shù)的最后一步是調(diào)用另一個(gè)函數(shù)。

function f(x){
  return g(x);
}

上面代碼中学搜，函數(shù)f的最后一步是調(diào)用函數(shù)g射赛，這就叫尾調(diào)用多柑。

以下三種情況，都不屬于尾調(diào)用楣责。

// 情況一
function f(x){
  let y = g(x);
  return y;
}

// 情況二
function f(x){
  return g(x) + 1;
}

// 情況三
function f(x){
  g(x);
}
//情況三等同于
function f(x){
  g(x);
  return undefined;
}

上面代碼中竣灌，情況一是調(diào)用函數(shù)g之后聂沙，還有賦值操作，所以不屬于尾調(diào)用初嘹，即使語(yǔ)義完全一樣及汉。情況二也屬于調(diào)用后還有操作，即使寫在一行內(nèi)屯烦。

尾調(diào)用不一定出現(xiàn)在函數(shù)尾部坷随，只要是最后一步操作即可

function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}

上面代碼中，函數(shù)m和n都屬于尾調(diào)用驻龟，因?yàn)樗鼈兌际呛瘮?shù)f的最后一步操作温眉。

二、尾調(diào)用優(yōu)化

尾調(diào)用之所以與其他調(diào)用不同迅脐，就在于它的特殊的調(diào)用位置芍殖。

我們知道，函數(shù)調(diào)用會(huì)在內(nèi)存形成一個(gè)“調(diào)用記錄”谴蔑，又稱“調(diào)用幀”（call frame）豌骏，保存調(diào)用位置和內(nèi)部變量等信息。如果在函數(shù)A的內(nèi)部調(diào)用函數(shù)B隐锭，那么在A的調(diào)用幀上方窃躲，還會(huì)形成一個(gè)B的調(diào)用幀。等到B運(yùn)行結(jié)束钦睡，將結(jié)果返回到A蒂窒，B的調(diào)用幀才會(huì)消失。如果函數(shù)B內(nèi)部還調(diào)用函數(shù)C荞怒，那就還有一個(gè)C的調(diào)用幀洒琢，以此類推。所有的調(diào)用幀褐桌，就形成一個(gè)“調(diào)用椝ヒ郑”（call stack）。

尾調(diào)用由于是函數(shù)的最后一步操作荧嵌，所以不需要保留外層函數(shù)的調(diào)用幀呛踊，因?yàn)檎{(diào)用位置、內(nèi)部變量等信息都不會(huì)再用到了啦撮，只要直接用內(nèi)層函數(shù)的調(diào)用幀谭网，取代外層函數(shù)的調(diào)用幀就可以了。

function f() {
  let m = 1;
  let n = 2;
  return g(m + n);
}
f();

// 等同于
function f() {
  return g(3);
}
f();

// 等同于
g(3);

上面代碼中赃春，如果函數(shù)g不是尾調(diào)用愉择，函數(shù)f就需要保存內(nèi)部變量m和n的值、g的調(diào)用位置等信息。但由于調(diào)用g之后薄辅，函數(shù)f就結(jié)束了要拂，所以執(zhí)行到最后一步抠璃，完全可以刪除f(x)的調(diào)用幀站楚，只保留g(3)的調(diào)用幀。

這就叫做“尾調(diào)用優(yōu)化”（Tail call optimization）搏嗡，即只保留內(nèi)層函數(shù)的調(diào)用幀窿春。如果所有函數(shù)都是尾調(diào)用，那么完全可以做到每次執(zhí)行時(shí)采盒，調(diào)用幀只有一項(xiàng)旧乞，這將大大節(jié)省內(nèi)存。這就是“尾調(diào)用優(yōu)化”的意義磅氨。

注意尺栖，只有不再用到外層函數(shù)的內(nèi)部變量，內(nèi)層函數(shù)的調(diào)用幀才會(huì)取代外層函數(shù)的調(diào)用幀烦租，否則就無(wú)法進(jìn)行“尾調(diào)用優(yōu)化”延赌。

function addOne(a){
  var one = 1;
  function inner(b){
    return b + one;
  }
  return inner(a);
}

上面的函數(shù)不會(huì)進(jìn)行尾調(diào)用優(yōu)化，因?yàn)閮?nèi)層函數(shù)inner用到了外層函數(shù)addOne的內(nèi)部變量one叉橱。

三挫以、尾遞歸

函數(shù)調(diào)用自身，稱為遞歸窃祝。如果尾調(diào)用自身掐松，就稱為尾遞歸。

遞歸非常耗費(fèi)內(nèi)存粪小，因?yàn)樾枰瑫r(shí)保存成千上百個(gè)調(diào)用幀大磺，很容易發(fā)生“棧溢出”錯(cuò)誤（stack overflow）。但對(duì)于尾遞歸來(lái)說探膊，由于只存在一個(gè)調(diào)用幀杠愧，所以永遠(yuǎn)不會(huì)發(fā)生“棧溢出”錯(cuò)誤。

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

上面代碼是一個(gè)階乘函數(shù)突想，計(jì)算n的階乘殴蹄，最多需要保存n個(gè)調(diào)用記錄，復(fù)雜度 O(n) 猾担。

如果改寫成尾遞歸袭灯，只保留一個(gè)調(diào)用記錄，復(fù)雜度 O(1) 绑嘹。

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

還有一個(gè)比較著名的例子稽荧，就是計(jì)算 Fibonacci 數(shù)列，也能充分說明尾遞歸優(yōu)化的重要性工腋。

非尾遞歸的 Fibonacci 數(shù)列實(shí)現(xiàn)如下姨丈。

function Fibonacci (n) {
  if ( n <= 1 ) {return 1};

  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(10) // 89
Fibonacci(100) // 超時(shí)
Fibonacci(500) // 超時(shí)

尾遞歸優(yōu)化過的 Fibonacci 數(shù)列實(shí)現(xiàn)如下畅卓。

function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
  if( n <= 1 ) {return ac2};

  return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}

Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity

由此可見，“尾調(diào)用優(yōu)化”對(duì)遞歸操作意義重大蟋恬，所以一些函數(shù)式編程語(yǔ)言將其寫入了語(yǔ)言規(guī)格翁潘。ES6 亦是如此，第一次明確規(guī)定歼争，所有 ECMAScript 的實(shí)現(xiàn)拜马，都必須部署“尾調(diào)用優(yōu)化”。這就是說沐绒，ES6 中只要使用尾遞歸俩莽，就不會(huì)發(fā)生棧溢出（或者層層遞歸造成的超時(shí)），相對(duì)節(jié)省內(nèi)存乔遮。

四扮超、遞歸函數(shù)的改寫

尾遞歸的實(shí)現(xiàn)，往往需要改寫遞歸函數(shù)蹋肮，確保最后一步只調(diào)用自身出刷。做到這一點(diǎn)的方法，就是把所有用到的內(nèi)部變量改寫成函數(shù)的參數(shù)括尸。比如上面的例子巷蚪，階乘函數(shù) factorial 需要用到一個(gè)中間變量total，那就把這個(gè)中間變量改寫成函數(shù)的參數(shù)濒翻。這樣做的缺點(diǎn)就是不太直觀屁柏，第一眼很難看出來(lái)，為什么計(jì)算5的階乘有送，需要傳入兩個(gè)參數(shù)5和1淌喻？

兩個(gè)方法可以解決這個(gè)問題。方法一是在尾遞歸函數(shù)之外雀摘，再提供一個(gè)正常形式的函數(shù)裸删。

function tailFactorial(n, total) {
  if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

function factorial(n) {
  return tailFactorial(n, 1);
}

factorial(5) // 120

上面代碼通過一個(gè)正常形式的階乘函數(shù)factorial，調(diào)用尾遞歸函數(shù)tailFactorial阵赠，看起來(lái)就正常多了涯塔。

函數(shù)式編程有一個(gè)概念，叫做柯里化（currying）清蚀，意思是將多參數(shù)的函數(shù)轉(zhuǎn)換成單參數(shù)的形式匕荸。這里也可以使用柯里化。

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ù)tailFactorial變?yōu)橹唤邮芤粋€(gè)參數(shù)的factorial榛搔。

第二種方法就簡(jiǎn)單多了，就是采用 ES6 的函數(shù)默認(rèn)值。

function factorial(n, total = 1) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5) // 120

上面代碼中践惑，參數(shù)total有默認(rèn)值1腹泌，所以調(diào)用時(shí)不用提供這個(gè)值。

總結(jié)一下尔觉，遞歸本質(zhì)上是一種循環(huán)操作凉袱。純粹的函數(shù)式編程語(yǔ)言沒有循環(huán)操作命令，所有的循環(huán)都用遞歸實(shí)現(xiàn)穷娱，這就是為什么尾遞歸對(duì)這些語(yǔ)言極其重要绑蔫。對(duì)于其他支持“尾調(diào)用優(yōu)化”的語(yǔ)言（比如 Lua，ES6）泵额，只需要知道循環(huán)可以用遞歸代替，而一旦使用遞歸携添，就最好使用尾遞歸嫁盲。

五、嚴(yán)格模式

ES6 的尾調(diào)用優(yōu)化只在嚴(yán)格模式下開啟烈掠，正常模式是無(wú)效的羞秤。

這是因?yàn)樵谡ＤＪ较拢瘮?shù)內(nèi)部有兩個(gè)變量左敌，可以跟蹤函數(shù)的調(diào)用棧瘾蛋。

• func.arguments：返回調(diào)用時(shí)函數(shù)的參數(shù)。
• func.caller：返回調(diào)用當(dāng)前函數(shù)的那個(gè)函數(shù)矫限。

尾調(diào)用優(yōu)化發(fā)生時(shí)哺哼，函數(shù)的調(diào)用棧會(huì)改寫，因此上面兩個(gè)變量就會(huì)失真叼风。嚴(yán)格模式禁用這兩個(gè)變量取董，所以尾調(diào)用模式僅在嚴(yán)格模式下生效。

function restricted() {
  'use strict';
  restricted.caller;    // 報(bào)錯(cuò)
  restricted.arguments; // 報(bào)錯(cuò)
}
restricted();

六无宿、尾遞歸優(yōu)化的實(shí)現(xiàn)

尾遞歸優(yōu)化只在嚴(yán)格模式下生效茵汰，那么正常模式下，或者那些不支持該功能的環(huán)境中孽鸡，有沒有辦法也使用尾遞歸優(yōu)化呢蹂午？回答是可以的，就是自己實(shí)現(xiàn)尾遞歸優(yōu)化彬碱。

它的原理非常簡(jiǎn)單豆胸。尾遞歸之所以需要優(yōu)化，原因是調(diào)用棧太多堡妒，造成溢出配乱，那么只要減少調(diào)用棧，就不會(huì)溢出。怎么做可以減少調(diào)用棧呢搬泥？就是采用“循環(huán)”換掉“遞歸”桑寨。

下面是一個(gè)正常的遞歸函數(shù)。

function sum(x, y) {
  if (y > 0) {
    return sum(x + 1, y - 1);
  } else {
    return x;
  }
}

sum(1, 100000)
// Uncaught RangeError: Maximum call stack size exceeded(…)

上面代碼中忿檩，sum是一個(gè)遞歸函數(shù)尉尾，參數(shù)x是需要累加的值，參數(shù)y控制遞歸次數(shù)燥透。一旦指定sum遞歸 100000 次沙咏，就會(huì)報(bào)錯(cuò)，提示超出調(diào)用棧的最大次數(shù)班套。

蹦床函數(shù)（trampoline）可以將遞歸執(zhí)行轉(zhuǎn)為循環(huán)執(zhí)行肢藐。

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

上面就是蹦床函數(shù)的一個(gè)實(shí)現(xiàn)，它接受一個(gè)函數(shù)f作為參數(shù)吱韭。只要f執(zhí)行后返回一個(gè)函數(shù)吆豹，就繼續(xù)執(zhí)行。注意理盆，這里是返回一個(gè)函數(shù)痘煤，然后執(zhí)行該函數(shù)，而不是函數(shù)里面調(diào)用函數(shù)猿规，這樣就避免了遞歸執(zhí)行衷快，從而就消除了調(diào)用棧過大的問題。

然后姨俩，要做的就是將原來(lái)的遞歸函數(shù)蘸拔，改寫為每一步返回另一個(gè)函數(shù)。

function sum(x, y) {
  if (y > 0) {
    return sum.bind(null, x + 1, y - 1);
  } else {
    return x;
  }
}

上面代碼中哼勇，sum函數(shù)的每次執(zhí)行都伪，都會(huì)返回自身的另一個(gè)版本。

現(xiàn)在积担，使用蹦床函數(shù)執(zhí)行sum陨晶，就不會(huì)發(fā)生調(diào)用棧溢出。

trampoline(sum(1, 100000))
// 100001

蹦床函數(shù)并不是真正的尾遞歸優(yōu)化帝璧，下面的實(shí)現(xiàn)才是先誉。

function tco(f) {
  var value;
  var active = false;
  var accumulated = [];

  return function accumulator() {
    accumulated.push(arguments);
    if (!active) {
      active = true;
      while (accumulated.length) {
        value = f.apply(this, accumulated.shift());
      }
      active = false;
      return value;
    }
  };
}

var sum = tco(function(x, y) {
  if (y > 0) {
    return sum(x + 1, y - 1)
  }
  else {
    return x
  }
});

sum(1, 100000)
// 100001

上面代碼中，tco函數(shù)是尾遞歸優(yōu)化的實(shí)現(xiàn)的烁，它的奧妙就在于狀態(tài)變量active褐耳。默認(rèn)情況下，這個(gè)變量是不激活的渴庆。一旦進(jìn)入尾遞歸優(yōu)化的過程铃芦，這個(gè)變量就激活了雅镊。然后，每一輪遞歸sum返回的都是undefined刃滓，所以就避免了遞歸執(zhí)行仁烹；而accumulated數(shù)組存放每一輪sum執(zhí)行的參數(shù)，總是有值的咧虎，這就保證了accumulator函數(shù)內(nèi)部的while循環(huán)總是會(huì)執(zhí)行卓缰。這樣就很巧妙地將“遞歸”改成了“循環(huán)”，而后一輪的參數(shù)會(huì)取代前一輪的參數(shù)砰诵，保證了調(diào)用棧只有一層征唬。

以上，引用于阮一峰《ECMAScript 6 入門》
http://es6.ruanyifeng.com/#docs/function