好几篇文章都说:尾调优化只有在严格模式下才有效。但是实际上,只不过是arguments和caller不能使用。在chrome和Firefox上测试是否使用严格模式并没有影响到尾调优化的迹象。而且在严格模式下使用ES6的函数默认参数反倒会抛出错误Uncaught SyntaxError: Illegal 'use strict' directive in function with non-simple parameter list。
function trampoline (fn) {
while (fn && fn instanceof Function) {
fn = fn();
}
return fn;
}
尾调优化函数
function tail (fn) {
var value,
active = false,
stack = [];
return function () {
stack.push(arguments);
if(!active) {
active = true;
while (stack.length) {
value = fn.apply(this, stack.shift());
}
active = false;
return value;
}
};
}
前段时间看阮一峰老师的ES6入门的“函数的扩展”部分,发现几个这门语言内置的一些性能优化的功能和算法,觉得挺有意思,想自己试试顺便也总结一下,但是一直没时间,今天抽空来写一写。
尾调优化(Tail-call optimization)
尾调优化是为了避免不断保留和创建新的调用栈,而在函数最后一步调用另一个函数。这是ES6才开始出现的概念,常用于尾递归。 最后一步的意义就在于:不需要保留当前函数的执行环境(阮老师的原文讲的是调用帧"call frame",但我的理解是执行环境另一种说法),在调用的下一个函数执行完毕并给出返回值后,直接再返回,类似于pipe。wiki
尾调优化有很多表现形式:
直接作为函数调用
对象方法调用
通过函数原型的
call
或者apply
方法来调用函数条件操作符、逻辑操作符和逗号操作符
以上4个操作符简写的尾调形式可以分别等价于如下四个:
语句中的尾调优化
暂未测试,详情见文末参考链接
尾递归(Tail-recursion)
尾递归就是利用尾调优化的特性,从语言机制上进行递归操作的优化,防止堆栈溢出(stack overflow)。
严格模式[有待考证]
好几篇文章都说:尾调优化只有在严格模式下才有效。但是实际上,只不过是
arguments
和caller
不能使用。在chrome和Firefox上测试是否使用严格模式并没有影响到尾调优化的迹象。而且在严格模式下使用ES6的函数默认参数反倒会抛出错误Uncaught SyntaxError: Illegal 'use strict' directive in function with non-simple parameter list
。尾递归优化实例
递归优化,在其他语言——比如C语言,就有递归转迭代的优化,而且递归和迭代是可以相互转换的,但是可能要牺牲空间复杂度,来换取更小的时间复杂度。这个时间复杂度就是递归优化的目的之一。
常见的递归实例
求自然数阶层:
经过尾调优化后:
求斐波那契数值:
经过尾调优化后:
经过尾调优化后,每次递归不需要保存其执行环境,只需要将一个末端的递归执行的返回值,逐层返回即可。这样就降低了内存占用,避免了堆栈溢出。
从以上两个例子可以看出,尾调优化后的递归,获取返回值的逻辑是逆向的。
尾调优化后再封装
factorial
函数的优化版,多了一个前置参数,但是往往不需要每次输入的,所以可以改写一下,封装起来。将上面尾调优化后的函数名改为
tailFactorial
函数内部调用
函数柯理化(currying)
ES6函数参数默认值
递归优化的实现
递归的迭代实现
递归优化的最佳实现应该是迭代。这里可以看到几种递归优化的对比表。
对上述
factorial
和fibonacci
函数转换为迭代实现。从以上代码可以看出:递归的迭代实现,跟递归实现的逻辑完全不同了;并且,每个递归迭代实现必须单独手动实现,没有统一的实现方式或辅助实现方式。
尾递归优化的实现
注意: 蹦床函数和尾调优化函数的尾递归优化实现,是在部分不支持尾调优化的情况下的手动实现。
蹦床函数(trampoline)
顾名思义,蹦床函数就是随着递归执行的开始和结束,调用栈会出现入栈、出栈效果,就像是在弹蹦床。
在使用蹦床函数辅助递归时,每次递归执行时都会保留上一次递归的激活对象(执行环境中的变量对象)的引用,执行本次递归完毕后,返回另一个待执行的递归,然后对上一次递归的激活对象的引用也就结束了。
可以看到其实就是把前面的尾递归改为,返回一个绑定了下一次递归参数的匿名函数。
尾调优化函数
实际上,蹦床函数并非真正的尾递归优化,以下才是:
上述
tail
函数的精妙之处在于,第一次调用返回的匿名函数(使用时分别赋值给了factorial
和fibonacci
)时,变量active
会“激活”,导致后续每次要进一步递归时都不成功,返回值都是undefined
,但是所有这些参数都被推入了stack
数组。因此,在第一次调用后,每次执行递归,都只是进入递归将这次递归接受的参数列表推入
stack
数组,直接返回而不进入下一轮递归;而返回以后由于stack
数组里有一个数组项,通过while
循环又处理新的参数列表,所以就会一直这样“进入递归->获得参数列表->返回->进入递归->...”的轮回,直到某轮递归没有向stack
数组推入参数。推入的参数在传入每轮递归时都会变化。总结
尾调优化,实际上就是指在函数内部,调用另一个函数得到的返回值,不用进行其他操作,直接当做自己的返回值返回的特殊情况。
收获
源码可以查看我的Gist
柯理化函数
蹦床函数
尾调优化函数
参考链接
tags: tail-call optimization, tail-recursion