详解JavaScript调用栈、尾递归和手动优化
调用栈(Call Stack)
调用栈(Call Stack)是一个基本的计算机概念,这里引入一个概念:栈帧。
栈帧是指为一个函数调用单独分配的那部分栈空间。
当运行的程序从当前函数调用另外一个函数时,就会为下一个函数建立一个新的栈帧,并且进入这个栈帧,这个栈帧称为当前帧。而原来的函数也有一个对应的栈帧,被称为调用帧。每一个栈帧里面都会存入当前函数的局部变量。
当函数被调用时,就会被加入到调用栈顶部,执行结束之后,就会从调用栈顶部移除该函数。并将程序运行权利(帧指针)交给此时栈顶的栈帧。这种后进后出的结构也就是函数的调用栈。
而在JavaScript里,可以很方便的通过console.trace()这个方法查看当前函数的调用帧
尾调用
说尾递归之前必须先了解一下什么是尾调用。简单的说,就是一个函数执行的最后一步是将另外一个函数调用并返回。
以下是正确示范:
// 尾调用正确示范1.0 function f(x){ return g(x); } // 尾调用正确示范2.0 function f(x) { if (x > 0) { return m(x) } return n(x); }
1.0程序的最后一步即是执行函数g,同时将其返回值返回。2.0中,尾调用并不是非得写在最后一行中,只要执行时,是最后一步操作就可以了。
以下是错误示范:
// 尾调用错误示范1.0 function f(x){ let y = g(x); return y; } // 尾调用错误示范2.0 function f(x){ return g(x) + 1; } // 尾调用错误示范3.0 function f(x) { g(x); // 这一步相当于g(x) return undefined }
1.0最后一步为赋值操作,2.0最后一步为加法运算操作,3.0隐式的有一句return undefined
尾调用优化
在调用栈的部分我们知道,当一个函数A调用另外一个函数B时,就会形成栈帧,在调用栈内同时存在调用帧A和当前帧B,这是因为当函数B执行完成后,还需要将执行权返回A,那么函数A内部的变量,调用函数B的位置等信息都必须保存在调用帧A中。不然,当函数B执行完继续执行函数A时,就会乱套。
那么现在,我们将函数B放到了函数A的最后一步调用(即尾调用),那还有必要保留函数A的栈帧么?当然不用,因为之后并不会再用到其调用位置、内部变量。因此直接用函数B的栈帧取代A的栈帧即可。当然,如果内层函数使用了外层函数的变量,那么就仍然需要保留函数A的栈帧,典型例子即是闭包。
在网上有很多关于讲解尾调用的博客文章,其中流传广泛的一篇中有这样一段。我不是很认同。
function f() { let m = 1; let n = 2; return g(m + n); } f(); // 等同于 function f() { return g(3); } f(); // 等同于 g(3);
以下为博客原文:上面代码中,如果函数g不是尾调用,函数f就需要保存内部变量m和n的值、g的调用位置等信息。但由于调用g之后,函数f就结束了,所以执行到最后一步,完全可以删除 f() 的调用记录,只保留 g(3) 的调用记录。
但我认为第一种中,也是先执行m+n这步操作,再调用函数g同时返回。这应当是一次尾调用。同时m+n的值也通过参数传入函数g内部,并没有直接引用,因此也不能说需要保存f内部的变量的值。
总得来说,如果所有函数的调用都是尾调用,那么调用栈的长度就会小很多,这样需要占用的内存也会大大减少。这就是尾调用优化的含义。
尾递归
递归,是指在函数的定义中使用函数自身的一种方法。函数调用自身即称为递归,那么函数在尾调用自身,即称为尾递归。
最常见的递归,斐波拉契数列,普通递归的写法:
function f(n) { if (n === 0 || n === 1) return n else return f(n - 1) + f(n - 2) }
这种写法,简单粗暴,但是有个很严重的问题。调用栈随着n的增加而线性增加,当n为一个大数(我测了一下,当n为100的时候,浏览器窗口就会卡死。。)时,就会爆栈了(栈溢出,stack overflow)。这是因为这种递归操作中,同时保存了大量的栈帧,调用栈非常长,消耗了巨大的内存。
接下来,将普通递归升级为尾递归看看。
function fTail(n, a = 0, b = 1) { if (n === 0) return a return fTail(n - 1, b, a + b) }
很明显,其调用栈为
fTail(5) => fTail(4, 1, 1) => fTail(3, 1, 2) => fTail(2, 2, 3) => fTail(1, 3, 5) => fTail(0, 5, 8) => return 5
被尾递归改写之后的调用栈永远都是更新当前的栈帧而已,这样就完全避免了爆栈的危险。
但是,想法是好的,从尾调用优化到尾递归优化的出发点也没错,然并卵:),让我们看看V8引擎官方团队的解释
Proper tail calls have been implemented but not yet shipped given that a change to the feature is currently under discussion at TC39.
意思就是人家已经做好了,但是就是还不能不给你用:)嗨呀,好气喔。
当然,人家肯定是有他的正当理由的:
- 在引擎层面消除尾递归是一个隐式的行为,程序员写代码时可能意识不到自己写了死循环的尾递归,而出现死循环后又不会报出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 aumulated = [] return function aumulator() { aumulated.push(arguments) if (!active) { active = true while (aumulated.length) { value = f.apply(this, aumulated.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 包装后返回的是一个新函数 aumulator,执行 f时实际执行的是这个函数。这种方法可以不用修改原递归函数,当调用递归时只用使用该方法转置一下便可解决递归调用的问题。
总结
尾递归优化是个好东西,但既然暂时用不上,那我们就该在平时编码的过程中,对使用到了递归的地方特别敏感,时刻避免出现死循环,爆栈等危险。毕竟,好的工具不如好的习惯。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持狼蚁SEO。
编程语言
- 机械手焊接机器人编程 机械手焊接设备编程
- vb数据库编程实例,vb做数据库
- tiobe世界编程语言排行榜,全球编程语言排行
- 成都java编程培训 成都it编程培训中心
- 编程基础培训,编程基础知识培训
- flash游戏编程基础教程,flash游戏开发教程
- 不会英语能学编程吗 不会英语可以学程序员吗
- 爱心代码编程C语言 爱心代码编程c语言公式
- c语言编程学习入门 c语言编程快速入门
- 西门子plc编程培训 西门子plc编程培训班
- 哪里可以学编程 台州哪里可以学编程
- 少儿编程哪个好 少儿编程哪个品牌好
- 编程是什么意思,图形编程是什么意思
- c语言编程软件下载,c语言编程软件在哪下载
- java编程软件下载,java编程下载手机版
- ug编程培训学校,ug编程培训教程