用户投稿本文章同时发布于：
MediumiT邦帮忙大家好，最近因为有一位朋友提到尾递迴，说这个优化技术「可以让递迴跑个一百万次都没问题」，惊呆的我，就花了些时间研究他，于是就产生了这个系列。
这个「高智能方程式」系列会以介绍以下为主：
演算法资料结构效能优化而为什么叫做高智能方程式，主要是因这是我童年很喜欢看的闪电霹雳车的香港名称，希望各位的code能够因为这些文章讨论而像阿斯拉一样越跑越快！绝对不是因为这部动画刚好有程式两个字的关係(｀∀´)
先说结论
其实他并不是很高深的技术，此优化就是：
将符合尾递迴形式的递迴转换成迭代
什么是尾递迴
尾递迴就是递迴的事物只能为函数自己
以程式码来说，如果我们有一个数列[1, 2, 3, 4, 5]，我们要把他们全部相加，以尾递迴的写法就是：
function recursive(n, ans = 0) { if (n === 0) return ans return recursive(n - 1, ans + n) // 回传的事物只有函数自己}如果你是以下的写法，就不算是尾递迴：
function recursive(n) { if (n === 0) return n return n + recursive(n - 1) // 回传的事物除了函数自己还有n}除此之外，如果像这样recursive(n - 1) + recursive(n - 1)回传两个自己也不行，
而当我们「正确的使用尾递迴」，我们就称为PTC(Proper Tail Calls)。
以费氏数列来举例，尾递迴帮助了我们什么
大家应该都还是得费氏数列的公式：
间单来说就是：
第一个数字为0，第二个数字为1，除了前两者，下一个数字都为前两个数字的和
费氏数列的前六个数为[0, 1, 1, 2, 3, 5]（第零个也是一个数），
我们现在要算出第六个数为多少，在程式上面非常直观的实作就是：
function fibonacci(n) { if (n === 0) return 0; if (n === 1) return 1; return fibonacci(n - 1) + fibonacci(n - 2)}console.log(fibonacci(5))// 得到5而在执行的时候我们的Stack(记忆体)，到底发生了什么事呢？我们可以在程式码里面加入debugger：
function fibonacci(n) { debugger if (n === 0) return 0; if (n === 1) return 1; return fibonacci(n - 1) + fibonacci(n - 2)}console.log(fibonacci(5))// 得到5在Chrome浏览器上执行后，Javascript就会停在debugger的地方，
这时候我们可以点选左方的箭头让Javascript继续递迴，这时你会看到右下角Call Stack的视窗产生了很多个fibonacci，那是因为：
在递迴未完成时，任何因递迴函数产生的Stack都不会被释放掉
所以整体执行会像下图：
当每次递迴时，都会再产生新的函数，而新的函数又会再产生新的函数，直到n === 0或n === 1的时候才不会产生新的函数，而是回传数值，当函数回传数值的时候，此函数才结束所有的任务，而释放Stack。
这样的做法会有两种问题：
Stack因为递迴佔着空间而消耗太大许多的重複的函数，例如fibonacci(1)就被呼叫了第五次所以如果你执行这个递迴1000000次，就会爆炸：
function fibonacci(n) { if (n === 0) return 0; if (n === 1) return 1; return fibonacci(n - 1) + fibonacci(n - 2)}console.log(fibonacci(1000000))
这时候如果我们启用尾递迴，他就会正常，我先贴上最后的答案：
function trampolines (fn) { return (...args) => { let result = fn(...args) while (typeof result === 'function') result = result() return result }}function fibonacci(n, ans = [0, 1]) { if (n === 0) return ans[0] if (n === 1) return ans[1] if (n <= 2) return ans[ans.length - 1] + ans[ans.length - 2] ans.push(ans[ans.length - 1] + ans[ans.length - 2]) return () => fibonacci(n - 1, ans);}console.log(trampolines(fibonacci)(1000000))// 虽然会显示Infinity，但这主要是因为数字太大了Javascript不支援，但是是可以运行的这倒是怎么运作的呢？我依序以下来分析：
迭代版尾递迴版配合trampolines来弥补Chrome没有尾递迴优化功能的尾递迴版首先，先以迭代的方式思考
我们可以通过数列的方式来思考，如果我们要取第六个数，可以列出以下数列
[0, 1, 1, 2, 3, 5]
第零个与第一个数是我们已知的，所以我们可以先预设好，剩下的数字每个值都是前两个直相加，所以我们可以写成以下程式码：
function fibonacci(n) { let ans = [0, 1] if (n === 0) return ans[0] if (n === 1) return ans[1] for(let i = 2; i <= n; i++) { ans.push(ans[ans.length - 1] + ans[ans.length - 2]) } return ans[ans.length - 1];}console.log(fibonacci(5))可以发现，其实这样的迭代已经与尾递迴的写法相同了，他们关键的差异就是：
迭代是宣告ans为一个区域变数，然后每次迭代都改变它尾递迴的写法是透过参数将ans带入下一次的递迴将迭代改成尾递迴版
把以上迭代的程式改为递迴形式，并将ans以参数带入下次递迴就会变成如下：
function fibonacci(n, ans = [0, 1]) { if (n === 0) return ans[0] if (n === 1) return ans[1] if (n <= 2) return ans[ans.length - 1] + ans[ans.length - 2] ans.push(ans[ans.length - 1] + ans[ans.length - 2]) return fibonacci(n - 1, ans);}console.log(fibonacci(5))而这时候，因为改为了PTC的形式，在以往个Chrome就会启用TCO(Tail Call Optimization)优化机制来释放Stack，会用「正规的尾递迴优化」，
但是现在Chrome不会启用TCO机制了
为什么呢？至于原因稍后会说明。
使用trampolines达到TCO的尾递迴版
既然现在Chrome没有TCO优化机制，要如何释放掉Stack，必须我们自己来实作，这时候我们会採用一个叫做trampolines的一个函数，他的作用就是：
将递迴转换成迭代
为了配合trampolines，我们需要将尾递迴做一点手脚，改为闭包，
为什么要这样呢？我们一行一行分析：
function trampolines (fn) { // 读取一开始的函数 return (...args) => { // 将函数的参数读取 let result = fn(...args) // 第一次执行函数，如果获得闭包函数，即进入while迴圈 while (typeof result === 'function') result = result() // 当每次执行函数时，ans的值都透过闭包保存，而因为已经回传了闭包，所以函数执行完毕，即释放Stack return result // 迭代result至不再回传闭包函数而是数值时，回传数值 }}function fibonacci(n, ans = [0, 1]) { if (n === 0) return ans[0] if (n === 1) return ans[1] if (n <= 2) return ans[ans.length - 1] + ans[ans.length - 2] ans.push(ans[ans.length - 1] + ans[ans.length - 2]) return () => fibonacci(n - 1, ans) // 如果回传不改为闭包，在let result = fn(...args)时就会一次执行完}console.log(trampolines(fibonacci)(5))使用闭包可以让递迴不一次执行完，并透过trampolines来执行且释放Stack，其关键如下：
Chrome原本不需要trampolines的帮忙
前面有提到Chrome一开始是支援的自动TCO的，所以我们在写以下函数写成PTC时：
function fibonacci(n, ans = [0, 1]) { if (n === 0) return ans[0] if (n === 1) return ans[1] if (n <= 2) return ans[ans.length - 1] + ans[ans.length - 2] ans.push(ans[ans.length - 1] + ans[ans.length - 2]) return fibonacci(n - 1, ans)}console.log(fibonacci(5))就会直接有trampolines配合闭包的效果，那为什么Chrome后来拿掉了呢？
大家可以看看Chrome引擎V8的讨论串，讨论串主要是认为，大多数的Javascript开发者，可能对「尾递迴」不了解，甚至不知道有这个东西，如果TCO机制只要发现PTC时就直接启动，那大多数人遇到的问题将会是：
侦错时没办法依照Stack慢慢去看递迴哪边出问题了，因为Stack早就被释放了，可是大多数开发者不知道有这机制
你可能会说：那如果开发者可以「明确的说我要尾递迴」再启动TCO不就好了嘛？
是的，所以TC39有加入了STC(Syntactic Tail Calls)的proposal，只要在递迴时加入continue，就是明确的跟引擎说：「请帮我启动TCO来优化尾递迴」，範例如下：
function factorial(n, acc = 1) { if (n === 1) { return acc; } return continue factorial(n - 1, acc * n)}但...此proposal后来没有被导入，然后，就没有然后惹(ﾉД`)
如果想要体验「正规的尾递迴优化」，目前唯一有支援TCO功能的只有Safari，在启动严谨模式(strict mode)会自动执行TCO，程式码如下：
'use strict';function fibonacci(n, ans = [0, 1]) { if (n === 0) return ans[0] if (n === 1) return ans[1] if (n <= 2) return ans[ans.length - 1] + ans[ans.length - 2] ans.push(ans[ans.length - 1] + ans[ans.length - 2]) return fibonacci(n - 1, ans)}console.log(fibonacci(1000000))// 虽然会显示Infinity，但这主要是因为数字太大了Javascript不支援，但是是可以运行的最后，我们需要尾递迴吗？
事实上，以「达到目标」来说，我们用尾递迴达到的效果，都可以透过迭代达到，因为尾递迴本质就是把递迴转为迭代，所以当你有天发现你在撰写的递迴，可以使用尾递迴时，那其实就是告诉你目前的函数可以转为迭代。
所以要选择尾递迴还是用迭代呢？我认为这与你目前撰写的区块风格有关，
如果你现在这个区块的风格多是FP的宣告式风格(Declarative)，那可以採用尾递迴，
如果多是指令式风格(Imperative)，那就可以採用迭代～
谢谢你的阅读，欢迎指教与讨论～
微信扫一扫打赏
支付宝扫一扫打赏
