ES6学习笔记10：函数尾调用优化
文章目录
- 尾调用优化
- 尾调用（Tail Call）是函数定义
- 尾调用优化
- 尾递归
- 定义
- 递归函数的改写
- 严格模式中的尾调用
- 尾递归优化的实现
- 原理
- 使用蹦床函数
- 尾递归优化
- 尾调用优化
- 尾调用（Tail Call）是函数定义
- 尾调用优化
- 尾递归
- 定义
- 递归函数的改写
- 严格模式中的尾调用
- 尾递归优化的实现
- 原理
- 使用蹦床函数
- 尾递归优化
尾调用优化
尾调用（Tail Call）是函数定义
尾调用（Tail Call）是函数式编程的一个重要的概念，就是指某一个函数的最后一步式调用另一个函数。
function f(x){return g(x);
}
这里的函数f的最后一步就是调用函数g,这就是尾调用。
以下情况都不是尾调用
// 一
function f(x){let y = g(x);return y;
}// 二
function f(x){return g(x) + 1;
}// 三
function f(x){g(x)；
}
尾调用不一定出现在函数尾部，只要是最后一步操作就可以了。
function f(x){if(x > 0){return m(x);}return n(x);
}
上面也是尾调用函数
尾调用优化
函数在调用的时候会在内存形成一个调用记录，又称“调用帧（call frame）”，保存调用位置和内部变量信息。如果函数A内部调用函数B,那么A的调用帧上方会形成一个B的调用帧。等B运行结束了，将结果返回给A,B的调用帧才会消失。如果函数B内部还调用函数C，那么还有一个C的调用帧，以此类推。所有的调用帧就形成一个“调用栈（call stack）”.
尾调用由于是函数的最后一个操作，所以不需要保留外层函数的调用帧，因为调用位置、内部变量等信息都不会再用到了，所以直接用内层函数的调用帧，取代外层函数的调用帧就可以了。
function f(){let m = 1;let n = 2;return g(m+n);}
f();
// 等同于
fucntion f(){return g(3);
}// 等同于
g(3);
上述代码中，如果g函数不是尾调用，f函数就需要保存内部变量m和n的值，g的调用位置等信息。但是由于调用了g函数以后，函数f就结束了，所以执行到最后一步完全可以删除f的调用帧，只保留g(3)的调用帧就可以了。
这就是“尾调用帧优化”，即只保留内层函数的调用帧。如果所有函数都是尾调用，那么完全可以做到每次执行的时候，调用帧只有一项，将大大节省内存，这就是尾调用帧优化的意义。
注意：
- 只有不再用到外层函数的内部变量，内层函数的调用帧才会取代外层函数的调用帧，否则就无法进行“尾调用优化”。
- 目前只有Safari浏览器支持尾调用优化，Chrome和Firefox都不支持
尾递归
定义
函数调用自身，称为递归。如果尾调用自身，就称为尾递归
递归非常耗费内存，因为需要同时保存成千上百的调用帧，很容易发生“栈溢出”错误（stack overflow）。但是由于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误（stack overflow）。
function f(n){if(n === 1) return 1;return n * f(n - 1);
}
console.log(f(5)); // 120
上面是阶乘运算，计算n的阶乘，最多保存n个调用记录，复杂度O(n).
如果改成尾递归，只保留一个调用记录，复杂度O(1).
function f(n, total){if(n === 1) return total;return f(n -1 ,n * total);
}
console.log(f(5,1));
递归函数的改写
尾递归的实现，往往需要改写成递归函数，确保最后一班只调用自身，做到这一点的方法，就是将所有用到内部变量改写成函数参数。
阶乘函数f需要用到一个中间变量total，那就把这个中间变量改写成函数的参数。这样做的缺点就是不太直观，不能第一眼就看出来。
- 解决不太直观，不能第一眼就看出来的方法：
- 在尾递归函数之外再提供一个正常形式的函数。
function f(n,total){if(n === 1) return 1;return f(n-1 ,n* total);
}function y(n){return f(n, 1);
}
上面代码通过一个正常形式的函数y调用了递归函数f.
柯里化（currying）：将多参数的函数转换成单参数的形式，上面也可以使用柯里化。
function currying(fn, n){return function (m) {return fn.call(this, m, n);}
}
function f(n, total){if(n === 1) return total;return f(n-1, n * total);
}const factorial = currying(f,1);console.log(factorial(5)); // 120
- 使用ES6的函数默认值
function f(n, total = 1){if(n === 1) return total;return f(n-1, n * total);
}
console.log(f(5)); // 120
严格模式中的尾调用
ES6的尾调用优化只在严格模式下开启，正常模式下是无效的。
在正常模式下，函数内部有两个变量，可以跟踪函数的调用栈。
func.arguments：返回调用函数的参数func.caller:返回调用当前函数的那个函数
尾调用优化时，函数的调用栈会改写，因此上面两个变量就会失真。严格模式中禁用这两个变量，所以尾调用模式仅在严格模式下生效。
function f(){'use strict';f.caller; // 报错f.arguments; // 报错
}
f();
尾递归优化的实现
在正常模式下实现尾递归：
原理
尾递归之所以需要优化，是因为调用栈太多，造成溢出，那么只要减少调用栈，就不会溢出。采用“循环” 代替“递归”。
使用蹦床函数
蹦床函数可以将递归执行转为循环执行
function trampoline(f){while(f && instanceof Function){f = f();}return f;
}
上面就是蹦床函数的一个实现，他接受一个函数f作为参数，只要f执行后返回一个函数，那就继续执行。注意：这里是返回一个函数，然后执行该函数，而不是函数里面调用函数，这样就避免了递归执行，从而解决调用栈过大的问题。
尾递归优化
function toc(f){var value;var active = false;var accimilated = [];return function accumulator(){accimilated.push(arguments);if(!active){active = true;while(accimilated.length){value = f.apply(this,accimilated.shift());}active = false;return value;}}
}
上述代码中，toc函数数尾递归优化的实现，奥妙就在状态变量active.默认情况下，这个变量是不激活的。一旦进入尾递归化的过程，这个变量就激活了。
尾调用优化
尾调用（Tail Call）是函数定义
尾调用（Tail Call）是函数式编程的一个重要的概念，就是指某一个函数的最后一步式调用另一个函数。
function f(x){return g(x);
}
这里的函数f的最后一步就是调用函数g,这就是尾调用。
以下情况都不是尾调用
// 一
function f(x){let y = g(x);return y;
}// 二
function f(x){return g(x) + 1;
}// 三
function f(x){g(x)；
}
尾调用不一定出现在函数尾部，只要是最后一步操作就可以了。
function f(x){if(x > 0){return m(x);}return n(x);
}
上面也是尾调用函数
尾调用优化
函数在调用的时候会在内存形成一个调用记录，又称“调用帧（call frame）”，保存调用位置和内部变量信息。如果函数A内部调用函数B,那么A的调用帧上方会形成一个B的调用帧。等B运行结束了，将结果返回给A,B的调用帧才会消失。如果函数B内部还调用函数C，那么还有一个C的调用帧，以此类推。所有的调用帧就形成一个“调用栈（call stack）”.
尾调用由于是函数的最后一个操作，所以不需要保留外层函数的调用帧，因为调用位置、内部变量等信息都不会再用到了，所以直接用内层函数的调用帧，取代外层函数的调用帧就可以了。
function f(){let m = 1;let n = 2;return g(m+n);}
f();
// 等同于
fucntion f(){return g(3);
}// 等同于
g(3);
上述代码中，如果g函数不是尾调用，f函数就需要保存内部变量m和n的值，g的调用位置等信息。但是由于调用了g函数以后，函数f就结束了，所以执行到最后一步完全可以删除f的调用帧，只保留g(3)的调用帧就可以了。
这就是“尾调用帧优化”，即只保留内层函数的调用帧。如果所有函数都是尾调用，那么完全可以做到每次执行的时候，调用帧只有一项，将大大节省内存，这就是尾调用帧优化的意义。
注意：
- 只有不再用到外层函数的内部变量，内层函数的调用帧才会取代外层函数的调用帧，否则就无法进行“尾调用优化”。
- 目前只有Safari浏览器支持尾调用优化，Chrome和Firefox都不支持
尾递归
定义
函数调用自身，称为递归。如果尾调用自身，就称为尾递归
递归非常耗费内存，因为需要同时保存成千上百的调用帧，很容易发生“栈溢出”错误（stack overflow）。但是由于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误（stack overflow）。
function f(n){if(n === 1) return 1;return n * f(n - 1);
}
console.log(f(5)); // 120
上面是阶乘运算，计算n的阶乘，最多保存n个调用记录，复杂度O(n).
如果改成尾递归，只保留一个调用记录，复杂度O(1).
function f(n, total){if(n === 1) return total;return f(n -1 ,n * total);
}
console.log(f(5,1));
递归函数的改写
尾递归的实现，往往需要改写成递归函数，确保最后一班只调用自身，做到这一点的方法，就是将所有用到内部变量改写成函数参数。
阶乘函数f需要用到一个中间变量total，那就把这个中间变量改写成函数的参数。这样做的缺点就是不太直观，不能第一眼就看出来。
- 解决不太直观，不能第一眼就看出来的方法：
- 在尾递归函数之外再提供一个正常形式的函数。
function f(n,total){if(n === 1) return 1;return f(n-1 ,n* total);
}function y(n){return f(n, 1);
}
上面代码通过一个正常形式的函数y调用了递归函数f.
柯里化（currying）：将多参数的函数转换成单参数的形式，上面也可以使用柯里化。
function currying(fn, n){return function (m) {return fn.call(this, m, n);}
}
function f(n, total){if(n === 1) return total;return f(n-1, n * total);
}const factorial = currying(f,1);console.log(factorial(5)); // 120
- 使用ES6的函数默认值
function f(n, total = 1){if(n === 1) return total;return f(n-1, n * total);
}
console.log(f(5)); // 120
严格模式中的尾调用
ES6的尾调用优化只在严格模式下开启，正常模式下是无效的。
在正常模式下，函数内部有两个变量，可以跟踪函数的调用栈。
func.arguments：返回调用函数的参数func.caller:返回调用当前函数的那个函数
尾调用优化时，函数的调用栈会改写，因此上面两个变量就会失真。严格模式中禁用这两个变量，所以尾调用模式仅在严格模式下生效。
function f(){'use strict';f.caller; // 报错f.arguments; // 报错
}
f();
尾递归优化的实现
在正常模式下实现尾递归：
原理
尾递归之所以需要优化，是因为调用栈太多，造成溢出，那么只要减少调用栈，就不会溢出。采用“循环” 代替“递归”。
使用蹦床函数
蹦床函数可以将递归执行转为循环执行
function trampoline(f){while(f && instanceof Function){f = f();}return f;
}
上面就是蹦床函数的一个实现，他接受一个函数f作为参数，只要f执行后返回一个函数，那就继续执行。注意：这里是返回一个函数，然后执行该函数，而不是函数里面调用函数，这样就避免了递归执行，从而解决调用栈过大的问题。
尾递归优化
function toc(f){var value;var active = false;var accimilated = [];return function accumulator(){accimilated.push(arguments);if(!active){active = true;while(accimilated.length){value = f.apply(this,accimilated.shift());}active = false;return value;}}
}
上述代码中，toc函数数尾递归优化的实现，奥妙就在状态变量active.默认情况下，这个变量是不激活的。一旦进入尾递归化的过程，这个变量就激活了。
备注：本文是自己学习阮一峰老师的《ECMAScript 6 入门》所做的笔记，大部分例子来源于此书。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！