0 喜欢

JS尾调用优化

admin
admin
2020-08-14 08:09:54 阅读 95

尾调用(Tail Call)是函数式编程的一个重要概念,本文介绍它的含义和用法。

概述

在计算机科学里,尾调用是指一个函数里的最后一个动作是一个函数调用的情形:即这个调用的返回值直接被当前函数返回的情形。这种情形下称该调用位置为尾位置。若这个函数在尾位置调用本身(或是一个尾调用本身的其他函数等等),则称这种情况为尾递归,是递归的一种特殊情形。尾调用不一定是递归调用,但是尾递归特别有用,也比较容易实现。

在程序运行时,计算机会为应用程序分配一定的内存空间;应用程序则会自行分配所获得的内存空间,其中一部分被用于记录程序中正在调用的各个函数的运行情况,这就是函数的调用栈。常规的函数调用总是会在调用栈最上层添加一个新的堆栈帧(stack frame,也翻译为“栈帧”或简称为“帧”),这个过程被称作“入栈”或“压栈”(意即把新的帧压在栈顶)。当函数的调用层数非常多时,调用栈会消耗不少内存,甚至会撑爆内存空间(栈溢出)[1],造成程序严重卡顿或意外崩溃。尾调用的调用栈则特别易于优化,从而可减少内存空间的使用,也能提高运行速度。[1]其中,对尾递归情形的优化效果最为明显,尤其是递归算法非常复杂的情形。[1]

一般来说,尾调用消除是可选的,可以用,也可以不用。然而,在函数编程语言中,语言标准通常会要求编译器或运行平台实现尾调用消除。这让程序员可以用递归取代循环而不丧失性能。

什么是尾调用

尾调用 (tail call) 指的是一个函数的最后一条语句也是一个返回调用函数的语句。在函数体末尾被返回的可以是对另一个函数的调用,也可以是对自身调用(即自身递归调用)

function foo(data) { a(data); return b(data); }

在这里,a(data)、b(data) 都是函数调用,但是 b(data) 是函数返回前的最后运行的东西,所以也是所谓的尾位置。然后,并非所有的尾调用都必须在一个函数语法上最后的位置。考虑:

function bar(data) { if ( a(data) ) { return b(data); } return c(data); }

在这里,b、c 的调用都在尾位置。这是因为尽管 b(data) 不在 bar 语法上最后的位置,它是 if 叙述其中一个分支最后的位置。

现在考虑以下代码:

function foo1(data) { return a(data) + 1; // 不是 } function foo2(data) { var ret = a(data); return ret; // 是 } function foo3(data) { var ret = a(data); return (ret === 0) ? 1 : ret; // 不是 }

在这里,a(data) 处于 foo2 的尾位置,但不处于 foo1 或 foo3 的尾位置。这是因为程序必须返回这2个 a 函数的调用以检查、更动 a 的返回值。

严格模式

ES6 的尾调用优化只在严格模式下开启,正常模式是无效的。
这是因为在正常模式下,函数内部有两个变量,可以跟踪函数的调用栈。

* func.arguments:返回调用时函数的参数。 * func.caller:返回调用当前函数的那个函数。

尾调用优化发生时,函数的调用栈会改写,因此上面两个变量就会失真。严格模式禁用这两个变量,所以尾调用模式仅在严格模式下生效。

function restricted() { 'use strict'; restricted.caller; // 报错 restricted.arguments; // 报错 }

什么是尾递归

若函数在尾位置调用自身(或是一个尾调用本身的其他函数等等),则称这种情况为尾递归。尾递归也是递归的一种特殊情形。尾递归是一种特殊的尾调用,即在尾部直接调用自身的递归函数。对尾递归的优化也是关注尾调用的主要原因。尾调用不一定是递归调用,但是尾递归特别有用,也比较容易实现。

尾调用优化示例

// 没有尾递归优化 function fibonacci(n) { if (n <= 1) return 1 return fibonacci(n - 1) + fibonacci(n - 2) } // 尾递归优化 function fibonacci2(n, ac1 = 1, ac2 = 1) { if (n <= 1) return ac2 return fibonacci2(n - 1, ac2, ac1 + ac2) } console.time("fibonacci") fibonacci(40) // 1103.526ms console.timeEnd("fibonacci") console.time("fibonacci2") fibonacci2(40) // 0.034ms console.timeEnd("fibonacci2")

关于作者
admin
admin
admin@ifront.net
 获得点赞 36
 文章阅读量 3671
文章标签