尾调用
1. 定义
尾调用是函数式编程中一个很重要的概念, 当一个函数执行时的最后一个步骤是返回另一个函数的调用, 这就叫做尾调用.
注意这里函数的调用方式是无所谓的, 以下方式均可:
函数调用: func(...)
方法调用: obj.method(...)
call 调用: func.call(...)
apply 调用: func.apply(...)
并且只有下列表达式会包含尾调用:
条件操作符: ? :
逻辑或: ||
逻辑与: &&
逗号: ,
依次举例:
- const a = x => x ? f() : g();
- // f() 和 g() 都在尾部.
- const a = () =>f() || g();
- // g()有可能是尾调用, f()不是
- // 因为上述写法和下面的写法等效:
- const a = () =>{
- const fResult = f(); // not a tail call
- if (fResult) {
- return fResult;
- } else {
- return g(); // tail call
- }
- }
- // 只有当 f()的结果为 falsey 的时候, g()才是尾调用
- const a = () =>f() && g();
- // g()有可能是尾调用, f()不是
- // 因为上述写法和下面的写法等效:
- const a = () =>{
- const fResult = f(); // not a tail call
- if (fResult) {
- return g(); // tail call
- } else {
- return fResult;
- }
- }
- // 只有当 f()的结果为 truthy 的时候, g()才是尾调用
- const a = () => (f() , g());
- // g()是尾调用
- // 因为上述写法和下面的写法等效:
- const a = () => {
- f();
- return g();
- }
2. 尾调用优化
函数在调用的时候会在调用栈 (call stack) 中存有记录, 每一条记录叫做一个调用帧(call frame), 每调用一个函数, 就向栈中 push 一条记录, 函数执行结束后依次向外弹出, 直到清空调用栈, 参考下图:
function foo () { console.log(111); }
function bar () { foo(); }
function baz () { bar(); }
baz();
造成这种结果是因为每个函数在调用另一个函数的时候, 并没有 return 该调用, 所以 JS 引擎会认为你还没有执行完, 会保留你的调用帧.
baz() 里面调用了 bar() 函数, 并没有 return 该调用, 所以在调用栈中保持自己的调用帧, 同时 bar() 函数的调用帧在调用栈中生成, 同理, bar() 函数又调用了 foo() 函数, 最后执行到 foo() 函数的时候, 没有再调用其他函数, 这里没有显示声明 return, 所以这里默认 return undefined.
foo() 执行完了, 销毁调用栈中自己的记录, 依次销毁 bar() 和 baz() 的调用帧, 最后完成整个流程.
如果对上面的例子做如下修改:
- function foo () { console.log(111); }
- function bar () { return foo(); }
- function baz () { return bar(); }
- baz();
这里要注意: 尾调用优化只在严格模式下有效.
在非严格模式下, 大多数引擎会包含下面两个属性, 以便开发者检查调用栈:
func.arguments: 表示对 func 最近一次调用所包含的参数
func.caller: 引用对 func 最近一次调用的那个函数
在尾调用优化中, 这些属性不再有用, 因为相关的信息可能以及被移除了. 因此, 严格模式 (strict mode) 禁止这些属性, 并且尾调用优化只在严格模式下有效.
如果尾调用优化生效, 流程图就会变成这样:
我们可以很清楚的看到, 尾调用由于是函数的最后一步操作, 所以不需要保留外层函数的调用记录, 只要直接用内层函数的调用记录取代外层函数的调用记录就可以了, 调用栈中始终只保持了一条调用帧.
这就叫做尾调用优化, 如果所有的函数都是尾调用的话, 那么在调用栈中的调用帧始终只有一条, 这样会节省很大一部分的内存, 这也是尾调用优化的意义.
尾递归
1. 定义
先来看一下递归, 当一个函数调用自身, 就叫做递归.
- function foo () {
- foo();
- }
上面这个操作就叫做递归, 但是注意了, 这里没有结束条件, 是死递归, 所以会报栈溢出错误的, 写代码时千万注意给递归添加结束条件.
那么什么是尾递归? 前面我们知道了尾调用的概念, 当一个函数尾调用自身, 就叫做尾递归.
- 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
上面是使用递归来计算阶乘的例子, 操作系统为 JS 引擎调用栈分配的内存是有大小限制的, 如果计算的数字足够大, 超出了内存最大范围, 就会出现栈溢出错误.
这里 500000 并不是临界值, 只是我用了一个足够造成栈溢出的数.
如果用尾递归来计算阶乘呢?
- '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); // 分情况
- // 注意, 虽然说这里启用了严格模式, 但是经测试, 在 Chrome 和 Firefox 下, 还是会报栈溢出错误, 并没有进行尾调用优化
- // Safari 浏览器进行了尾调用优化, factorial(500000, 1)结果为 Infinity, 因为结果超出了 JS 可表示的数字范围
- // 如果在 node v6 版本下执行, 需要加 --harmony_tailcalls 参数, node --harmony_tailcalls test.js
- // node 最新版本已经移除了 --harmony_tailcalls 功能
通过尾递归, 我们把复杂度从 O(n)降低到了 O(1), 如果数据足够大的话, 会节省很多的计算时间. 由此可见, 尾调用优化对递归操作意义重大, 所以一些函数式编程语言将其写入了语言规格.
避免改写递归函数
尾递归的实现, 往往需要改写递归函数, 确保最后一步只调用自身. 要做到这一点, 需要把函数内部所有用到的中间变量改写为函数的参数, 就像上面的 factorial()函数改写一样.
这样做的缺点就是语义不明显, 要计算阶乘的函数, 为什么还要另外传入一个参数叫 total? 解决这个问题的办法有两个:
1. ES6 参数默认值
- '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. 用一个符合语义的函数去调用改写后的尾递归函数
- 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
上面这种写法其实有点类似于做了一个函数科里化, 但不完全符合科里化的概念. 函数科里化是指把接受多个参数的函数转换为接受一个单一参数 (最初函数的第一个参数) 的函数, 并且返回接受余下参数且返回结果的新函数.
概念看着很绕口, 我们来个例子感受一下:
- // 普通加法函数
- function add(x, y, z) {
- return x + y + z;
- }
- add(1, 2, 3); // 6
- // 改写为科里化加法函数
- function add(x) {
- return function(y) {
- return function(z) {
- return x + y + z;
- }
- }
- }
- add(1)(2)(3); // 6
可以看到, 科里化函数通过闭包找到父作用域里的变量, 最后依次相加输出结果. 通过这个例子, 可能看不出为什么要用科里化, 有什么好处, 这个我们以后再谈, 这里先引出一个概念.
是把接受多个参数的函数变换成接受一个单一参数 (最初函数的第一个参数) 的函数, 并且返回接受余下的参数且返回结果的新函数的技术.
如果用科里化改写求阶乘的例子:
- // 科里化函数
- function curry(fn) {
- var _fnArgLength = fn.length;
- function wrap(...args) {
- var _args = args;
- var _argLength = _args.length;
- // 如果传的是所有参数, 直接返回 fn 调用
- 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;
- }
- // 尾递归函数
- 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
我个人认为, 这种写法其实不是科里化, 因为并没有将多参数的 tailFacrotial 改写为接受单参数的形式, 只是换了一种写法, 和下面这样写意义是一样的:
- 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
结束
这篇文章我们主要讨论了尾调用优化和科里化. 要注意的是, 经过测试, Chrome 和 Firefox 并没有对尾调用进行优化, Safari 对尾调用进行了优化. Node 高版本也已经去除了通过 --harmony_tailcalls 参数启用尾调用优化.
有任何问题, 欢迎大家留言讨论, 另附我的博客网站, 快来呀~~ blog.liuxuan.site
参考链接
http://www.ruanyifeng.com/blog/2015/04/tail-call.html https://juejin.im/post/5a4d898a518825698e7277d1 https://github.com/lamdu/lamdu/issues/90
来源: https://juejin.im/post/5acdd7486fb9a028ca53547c