JS—尾调⽤优化、尾递归、递归函数的改写
1.尾调⽤（Tail Call）
尾调⽤是函数式编程的⼀个重要概念，本⾝⾮常检点。就是：某个函数的最后⼀步是调⽤另⼀个函数
function f(x){
return g(x);
}
函数f的最后⼀步是调⽤函数g，这就叫尾调⽤。
以下情况，都不属于尾调⽤：
1// 情况⼀
2function f(x) {
3        let y = g(x)
4return y
5    }
6
7// 情况⼆
8function f(x) {
9return g(x) + 1
10    }
11
12// 情况三
13function f(x) {
14        g(x)
15    }
上⾯代码中：
情况⼀：调⽤函数g之后，还有赋值操作，所以不属于尾调⽤
情况⼆：调⽤后还有操作
情况三等同于：
1function f(x) {
2if (x > 0) {
3return m(x)
4  }
5return n(x);
6 }
尾调⽤不⼀定出现在函数尾部，只要是最后⼀步操作即可：
1function f(x) {
2if (x > 0) {
3return m(x)
4  }
5return n(x);
6 }
上⾯代码中：函数m和n都属于尾调⽤，因为它们都是函数f的最后⼀步操作
2.尾调⽤优化
尾调⽤之所以与其他调⽤不同，就在于它的特殊的调⽤位置。
（1）正常函数调⽤：
  函数调⽤会在内存形成⼀个“调⽤记录”，⼜称“调⽤帧（call frame）”，保存调⽤位置和内部变量等信息，调⽤帧可以理解为栈中的⼀格，如下所⽰：
  如⼀个函数：
function a(){
b()
}
上⾯函数a执⾏的过程如下：
执⾏到a()时，a被推⼊调⽤帧底部
执⾏到a()中的b()⽅法时，b被压⼊a上⽅
b()执⾏结束，b()从调⽤栈中移除
a()执⾏结束，a()从调⽤栈移除，调⽤栈清空
以此类推，多个执⾏语句先后⼊栈出栈
（2）函数尾调⽤
  尾调⽤由于是函数的最后⼀步操作，所以不需要保留外层函数的调⽤帧，因为调⽤位置、内部变量等信息都不会再⽤到了，只要直接⽤内层函数的调⽤帧，取代外层函数的调⽤帧就可以了。
1function f(){
2    let n = 1
3    let m = 2
4return g(n + m)
5 }
6 f()
7
8// 等同于
9function f(){
10return g(3)
11 }
12 f()
13
14// 等同于
15 g(3)　
上⾯代码，如果函数g不是尾调⽤，函数f就需要保存内部变量m和n的值，g的调⽤位置等信息。但是由于调⽤g之后，函数f就结束了，所以执⾏到最后⼀步，完全可以删除f(x)的调⽤帧，只保留g(3)的调⽤帧。这就叫尾调⽤优化（Tail call optimization），即只保留内层函数的调⽤帧，如果所有函数都是尾调⽤，那么完全可以做到每次执⾏时，调⽤帧只有⼀项，这将⼤⼤节省内存。这就是“尾调⽤优化“的意义。
注意：只有不再⽤到外层函数的内部变量，内层函数的调⽤帧才会取代外层函数的调⽤帧，否则⽆法进⾏”尾调⽤优化“
1function addOne(a){
2var one = 1;
3function inner(b){
4return b + one;
5  }
网站底部代码js特效6return inner(a);
7 }
因为内层函数inner⽤到了外层函数addOne的内部变量one。
注意：
⽬前⾃会有Safari浏览器⽀持尾调⽤优化，Chrome和Fiefox都不⽀持
ES6的尾调⽤优化只在严格模式下开启，正常模式下是⽆效的（因为在正常模式下，函数内部有两个变量，可以跟踪函数的调⽤栈）func.arguments：返回调⽤时函数的参数
func.caller：返回调⽤当前函数的那个函数
尾调⽤优化发⽣时，函数的调⽤栈会改写，因此上⾯两个变量就会失真。严格模式下禁⽤了这两个变量，所以尾调⽤优化仅在严格模式下⽣效
3.尾递归
函数调⽤⾃⾝，称为递归，如果尾调⽤⾃⾝，就称为尾递归
⾮常耗费内存，因为需要同时保存成千上百个调⽤帧，很容易法伤”栈溢出“（stack overflow）。但是对于尾递归来说，由于只存在⼀个调⽤帧，所以永远不会发⽣栈溢出错误。
（1）⽰例：计算阶乘
⾮尾调⽤：
1function factorial(n) {
2if (n === 1) return 1;
3return n * factorial(n -1)
4 }
5 factorial(5)
上⾯代码，计算n的阶乘，最多需要保存n个调⽤记录，复杂度O(n)
尾调⽤：
1function factorial(n,total) {
2if (n === 1) return total;
3return factorial(n - 1, n * total)
4 }
5
6 factorial(5,1)  // 120
改成尾递归，只保留⼀个调⽤记录，复杂度O（1）
（2）⽰例：计算斐波那契数列
1function Fibonacci (n) {
2if ( n <= 1 ) {return 1};
3
4return Fibonacci(n - 1) + Fibonacci(n - 2);
5 }
6
7 Fibonacci(10) // 89
8 Fibonacci(100) // 超时
9 Fibonacci(500) // 超时
尾递归优化：
1function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
2if( n <= 1 ) {return ac2};
3
4return Fibonacci2 (n - 1, ac2, ac1 + ac2);
5 }
6
7 Fibonacci2(100) // 573147844013817200000
8 Fibonacci2(1000) // 7.0330367711422765e+208
9 Fibonacci2(10000) // Infinity
由此可见，”尾调⽤优化“对递归操作意义重⼤，所以⼀些函数式编程语⾔将其写⼊了语⾔规格。ES6也是如此，第⼀次明确规定，所有ECMAScript的实现，都必须部署"尾调⽤优化"。这就是说，ES6中只要使⽤尾递归，就不会发⽣栈溢出（或者层层递归造成的超时），相对节省内存。
（3）递归函数的改写
尾递归的实现，往往需要改写递归函数，确保最后⼀步只调⽤⾃⾝。如何做到这⼀点：
①把所有⽤到的内部变量改写成函数的参数（缺点：不太直观）
  如上⾯的阶乘函数factorial需要⽤到⼀个中间变量total，那就把这个中间⽐那辆改写成函数的参数。 
有两种⽅法可以解决这个问题：
⽅法⼀：再尾递归函数之外，再提供⼀个正常形式的函数
1function tailFactorial(n, total) {
2if (n === 1) return total;
3return tailFactorial(n - 1, n * total);
4 }
5
6function factorial(n) {
7return tailFactorial(n, 1);
8 }
9
10 factorial(5) // 120
上⾯代码通过⼀个正常形式的阶乘函数，调⽤尾递归函数。看起来会正常⼀点。
函数柯⾥化：是函数式编程中的⼀个概念，意思是将多参数的函数转换成单参数的形式。这⾥也可以使⽤柯⾥化：
1function currying(fn,n){
2return function(m){
3return fn.call(this,m,n)
4    }
5 }
6
7function tailFactorial(n,total){
8if(n === 1) return total
9return tailFactorial(n -1, n * total)
10 }
11
12 const factorial = currying(tailFactorial, 1)
13
14 factorial(5)
⽅法⼆：ES6的函数默认值
这种⽅法⽐较简单。
1function factorial(n, total = 1) {
2if (n === 1) return total;
3return factorial(n - 1, n * total);
4 }
5
6 factorial(5) // 120
参数total有默认值1，所以调⽤时不⽤提供这个值
总结⼀下：递归本质上是⼀种循环操作。纯粹的函数式编程语⾔没有循环操作命令，所有的循环都⽤递归实现，这就是为什么尾递归对这些语⾔极其重要。对于其他⽀持“尾调⽤优化”的语⾔（⽐如 Lua，ES6），只需要知道循环可以⽤递归代替，⽽⼀旦使⽤递归，就最好使⽤尾递归。
（4）尾递归优化的实现
尾递归优化只在严格模式下⽣效，正常情况下，或者那些不⽀持该功能的环境中，可以⾃⼰实现尾递归优化。
原理：
  尾递归之所以需要优化，原因是调⽤栈太多，造成溢出，那么只要减少调⽤栈，就不会溢出。如何实现减少调⽤栈？就是：使⽤“循环”换掉“递归”
⼀个正常的递归函数：
1function sum(x, y) {
2if (y > 0) {
3return sum(x + 1, y - 1);
4  } else {
5return x;
6  }
7 }
8
9 sum(1, 100000)
10// Uncaught RangeError: Maximum call stack size exceeded(…)
上⾯代码中，sum是⼀个递归函数，参数x是需要累加的值，参数y控制递归次数。⼀旦指定sum递归 100000 次，就会报错，提⽰超出调⽤栈的最⼤次数。
蹦床函数（trampoline）可以将递归执⾏转为循环执⾏。
1function trampoline(f) {
2while (f && f instanceof Function) {
3    f = f();
4  }
5return f;
6 }
上⾯就是蹦床函数的⼀个实现，它接受⼀个函数f作为参数。只要f执⾏后返回⼀个函数，就继续执⾏。注意，这⾥是返回⼀个函数，然后执⾏该函数，⽽不是函数⾥⾯调⽤函数，这样就避免了递归执⾏，从⽽就消除了调⽤栈过⼤的问题。
然后，要做的就是将原来的递归函数，改写为每⼀步返回另⼀个函数。
1function sum(x, y) {
2if (y > 0) {
3return sum.bind(null, x + 1, y - 1);
4  } else {
5return x;
6  }
7 }
上⾯代码中，sum函数的每次执⾏，都会返回⾃⾝的另⼀个版本。
现在，使⽤蹦床函数执⾏sum，就不会发⽣调⽤栈溢出。
trampoline(sum(1, 100000))
// 100001
蹦床函数并不是真正的尾递归优化，下⾯的实现才是。
1function tco(f) {
2var value;
3var active = false;
4var accumulated = [];
5
6return function accumulator() {
7    accumulated.push(arguments);
8if (!active) {
9      active = true;
10while (accumulated.length) {
11        value = f.apply(this, accumulated.shift());
12      }
13      active = false;
14return value;
15    }
16  };
17 }
18
19var sum = tco(function(x, y) {
20if (y > 0) {
21return sum(x + 1, y - 1)
22  }
23else {
24return x
25  }
26 });
27
28 sum(1, 100000)
29// 100001
上⾯代码中，tco函数是尾递归优化的实现，它的奥妙就在于状态变量active。默认情况下，这个变量是不激活的。⼀旦进⼊尾递归优化的过程，这个变量就激活了。然后，每⼀轮递归sum返回的都是undefined，所以就避免了递归执⾏；⽽accumulated数组存放每⼀轮sum执⾏的参数，总是有值的，这就保证了accumulator函数内部的while循环总是会执⾏。这样就很巧妙地将“递归”改成了“循环”，⽽后⼀轮的参数会取代前⼀轮的参数，保证了调⽤栈只有⼀层。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。