尾調(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ì)消失。如果還是內(nèi)部還調(diào)用函數(shù)C，那就還有一個(gè)C的調(diào)用幀，以此類推。所有的調(diào)用幀，就會(huì)形成一個(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)
    }
    //等同于
    function f() {
        return g(3);
    }
    f()
        //等同于
    g(3)

上面代碼中，如果函數(shù)g不是尾調(diào)用，函數(shù)f就需要保存內(nèi)部變量m和n的值，但是由于調(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)用幀，否則無法進(jìn)行“尾調(diào)用優(yōu)化”

    function addOne(a) {
        let 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ì)于尾遞歸來說，由于只存在一個(gè)調(diào)用幀。所以永遠(yuǎn)不會(huì)發(fā)生“棧溢出”錯(cuò)誤

舉個(gè)??

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

    console.log(factorial(5)); // 120
    console.log(factorial(4)); // 24

上面代碼是一個(gè)階乘函數(shù)，計(jì)算n的階乘，最多需要保存n個(gè)調(diào)用記錄。如果改寫成尾遞歸，只保留一個(gè)調(diào)用記錄。

    function factorial(n, total) {
        if (n === 1) return total;
        return factorial(n - 1, n * total);
    };
    console.log(factorial(5, 1)); // 120
    console.log(factorial(4, 1)); // 24

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

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

    console.log(Fibonacci(10)); //89
    console.log(Fibonacci(100)); //堆棧溢出

尾調(diào)用優(yōu)化過后的Fibonacci數(shù)列實(shí)現(xiàn)如下

    function Fibonacci(n, ac1 = 1, ac2 = 1) {
        if (n <= 1) { return ac2 };
        return Fibonacci(n - 1, ac2, ac1 + ac2);
    }

    console.log(Fibonacci(10)); //89
    console.log(Fibonacci(30)); //1346269
    console.log(Fibonacci(100)); //10946

“尾調(diào)用優(yōu)化”對(duì)遞歸操作意義重大，所以一些函數(shù)式編程語言將其寫入了語言規(guī)格。第一次明確規(guī)定，所有ECMAScript的實(shí)現(xiàn)，都必須部署“尾調(diào)用優(yōu)化”。就是說，ES6中只要使用尾遞歸，就不會(huì)發(fā)生棧溢出，相對(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)就是不太只管，第一眼很難看出來，為什么計(jì)算5的階乘，需要傳入兩個(gè)參數(shù)5和1.

    function tailFactorial(n, total) {
        if (n === 1) return total;
        console.log(n - 1, n * total);
        /**
         * 4 5
         * 3 20
         * 2 60
         * 1 120
         */
        return tailFactorial(n - 1, n * total)
    }

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

    factorial(5)

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

函數(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);
    console.log(factorial(5));//120

上面函數(shù)通過柯里化，將尾遞歸函數(shù)tailFactorial變?yōu)橹唤邮找粋€(gè)參數(shù)的factorial
第二種方法就簡單多了，直接用ES6的函數(shù)默認(rèn)值。

    function factorial(n, total = 1) {
        if (n === 1) return total;
        return factorial(n - 1, n * total)
    }
    //上面方法中，參數(shù)total有默認(rèn)值1，所以調(diào)用時(shí)不用提供這個(gè)值
    console.log(factorial(5)); //120

遞歸本質(zhì)上是一種循環(huán)操作。純粹的函數(shù)式編程語言沒有循環(huán)操作命令，所有的循環(huán)都用遞歸實(shí)現(xiàn)，這就是為什么尾遞歸對(duì)這些語言極其重要，對(duì)于其他支持“尾調(diào)用優(yōu)化”的語言，只需要循環(huán)可以用遞歸代替，而一旦使用遞歸，最好就用尾遞歸

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

尾遞歸優(yōu)化只有在嚴(yán)格模式下生效，在正常模式下，或者不支持該功能的語言環(huán)境中，需要自己實(shí)現(xiàn)尾調(diào)用優(yōu)化。
原理是尾遞歸之所以需要優(yōu)化，原因是調(diào)用棧太多，造成溢出。那么只要減少調(diào)用棧，就不會(huì)溢出。

采用“循環(huán)”替代“遞歸”
一個(gè)正常的遞歸函數(shù)：

    function sum(x, y) {
        if (y > 0) {
            return sum(x + 1, y - 1)
        } else {
            return x
        }
    }
    console.log(sum(1, 100000)); 
    //RangeError: Maximum call stack size exceeded

上面這個(gè)sum是一個(gè)遞歸函數(shù)，參數(shù)x是需要累加的值，參數(shù)y控制遞歸次數(shù)，一旦sum遞歸100000次。就會(huì)報(bào)錯(cuò)，提示超出調(diào)用棧的最大次數(shù)
將遞歸執(zhí)行轉(zhuǎn)為循環(huán)執(zhí)行

    function trampoline(f) {
        /**
         * 接收一個(gè)函數(shù)f作為參數(shù)，只要f執(zhí)行后返回一個(gè)函數(shù)就繼續(xù)執(zhí)行
         * 這里是返回一個(gè)函數(shù)，然后執(zhí)行該函數(shù)，而不是函數(shù)里面調(diào)用函數(shù)
         * 這樣就避免了遞歸執(zhí)行，從而消除報(bào)錯(cuò)問題
         *  */
        while (f && f instanceof Function) {
            f = f();
        }
        return f;
    }
    //修改原來的sum函數(shù)，使得sum函數(shù)的每次執(zhí)行，都會(huì)返回自身另一個(gè)版本
    function sum(x, y) {
        if (y > 0) {
            return sum.bind(null, x + 1, y - 1)
        } else {
            return x
        }
    }
    console.log(trampoline(sum(1, 100000))); //100001

但是上面的trampoline函數(shù)并不是真正的尾調(diào)用優(yōu)化，下面實(shí)現(xiàn)才是

    function tco(f) {
        let value;
        //默認(rèn)情況下，這個(gè)狀態(tài)變量active不激活（1），
        let active = false;
        let accumulated = [];
        return function accumulator() {
            //accumulated數(shù)組存放每一輪sum執(zhí)行的參數(shù)（3）
            accumulated.push(arguments);

            if (!active) {
                //一旦進(jìn)入尾遞歸優(yōu)化的過程，這個(gè)變量激活（2）
                active = true;
                while (accumulated.length) {
                    //每一輪遞歸，sum返回的都是undefined，避免了遞歸執(zhí)行
                    //而accumulated數(shù)組存放的每一輪的sum執(zhí)行的參數(shù)，總是有值的，保障了while循環(huán)總是會(huì)執(zhí)行
                    value = f.apply(this, accumulated.shift());
                    //shift() 方法用于把數(shù)組的第一個(gè)元素從其中刪除，并返回第一個(gè)元素的值。
                }
                active = false;
                return value;
            }
        }
    }
    let sum = tco((x, y) => {
        if (y > 0) {
            return sum(x + 1, y - 1)
        } else {
            return x
        }
    });

    console.log(sum(1, 100000)); //100001