在引擎层面消除尾递归是一个隐式的行为,程序员写代码时可能意识不到自己写了死循环的尾递归,而出现死循环后又不会报出stack overflow的错误,难以辨别。
堆栈信息会在优化的过程中丢失,开发者调试非常困难。
道理我都懂,但是不信邪的我拿nodeJs(v6.9.5)手动测试了一下:
好的,我服了
手动优化
虽然我们暂时用不上ES6的尾递归高端优化,但递归优化的本质还是为了减少调用栈,避免内存占用过多,爆栈的危险。而俗话说的好,一切能用递归写的函数,都能用循环写——尼克拉斯·夏,如果将递归改成循环的话,不就解决了这种调用栈的问题么。
方案一:直接改函数内部,循环执行
function fLoop(n, a = 0, b = 1) { while (n--) { [a, b] = [b, a + b] } return a }
这种方案简单粗暴,缺点就是没有递归的那种写法比较容易理解。
方案二:Trampolining(蹦床函数)
function trampoline(f) { while (f && f instanceof Function) { f = f() } return f } function f(n, a = 0, b = 1) { if (n > 0) { [a, b] = [b, a + b] return f.bind(null, n - 1, a, b) } else { return a } } trampoline(f(5)) // return 5
这种写法算是容易理解一些了,就是蹦床函数的作用需要仔细看看。缺点还有就是需要修改原函数内部的写法。
方案三:尾递归函数转循环方法
function tailCallOptimize(f) { let value let active = false const accumulated = [] return function accumulator() { accumulated.push(arguments) if (!active) { active = true while (accumulated.length) { value = f.apply(this, accumulated.shift()) } active = false return value } } } const f = tailCallOptimize(function(n, a = 0, b = 1) { if (n === 0) return a return f(n - 1, b, a + b) }) f(5) // return 5
经过 tailCallOptimize 包装后返回的是一个新函数 accumulator,执行 f时实际执行的是这个函数。这种方法可以不用修改原递归函数,当调用递归时只用使用该方法转置一下便可解决递归调用的问题。
总结
尾递归优化是个好东西,但既然暂时用不上,那我们就该在平时编码的过程中,对使用到了递归的地方特别敏感,时刻避免出现死循环,爆栈等危险。毕竟,好的工具不如好的习惯。