摘要：该文首先讲解了“尾调用”的概念和性质，介绍了“尾调用优化”的实用意义。“尾调用”与“递归”的结合，引出了“尾递归”。随后以JS环境下的斐波那契数列（Fibonacci）为例探讨了其使用方法与改造技巧，最后简单讲述了尾递归优化的实现原理。

关键词：尾调用;优化;递归;尾递归;柯里化

中图分类号：TP311      文献标识码：A

文章编号：1009-3044（2020）17-0208-03

Abstract： This paper introduces the definition and character of tail call， as well as the utility of Tail Call Optimization（TCO）. The combination of tail call and recursion generates “tail recursion”. Next， I discuss the method of use and transformation skill through the example of Fibonacci in the JS programming environment. Last， the implementation principle of TCO is explained briefly.

Key words： tail call; optimization; recursion; tail recursion; currying

尾调用（Tail Call）是函数式编程的一个重要概念。当一个函数处于（另）一个函数的尾部，准确地说，是在最后一条返回语句（return）中的时候，我们称之为尾调用。从主调函数的角度看，执行的最后一个动作是返回（另）一个函数的运行结果;从被调函数的角度看，运行结果直接被另一个函数返回了。通常情况下，一个函数的返回值是一个简单的数值;而在尾调用中，如果不考虑递归的话，返回的是另一个函数的运行结果。如：

值得注意的是，由于程序在返回时可能存在分支结构，因此尾调用不一定是字面上的最后一条语句;这里的“尾”字，指的是程序执行的最后一个动作，我们称该调用位置是函数的尾位置。举个简单的例子：

不难看出，这里的尾位置是对a（）的调用和返回就不是函数x书面上的最后一条语句。如果情况稍复杂些，则：

这里的函数y和z都不是尾调用，即使z函数在语义上没有变化。当然，如果一个函数没有return，也就是不返回数值的话，就更谈不上尾调用了。

在程序运行时，计算机会为应用程序分配一定的内存空间;应用程序则会自行分配所获得的内存空间，其中一部分被用于记录程序中正在调用的各个函数的运行情况，这就是函数的调用栈（call stack）。一般的函数调用总是会在调用栈最上层添加一个新的栈帧（stack frame），这个过程被称作“入栈”或“压栈”（push）。当函数的调用层数非常多时，调用栈会消耗掉不少内存，甚至会撑爆栈空间造成溢出，导致程序严重卡顿或意外崩溃。

在传统的程序调用的过程中，计算机必须“记住”调用函数的返回位置，才能在调用结束后返回该位置继续执行后续命令，该位置信息（即下一条指令的内存地址）一般被存放在调用栈上。与之不同的是，在尾调用这种特殊的情形中，由于调用下级函数以后上级函数就结束了，所以执行到最后一步，计算机可以不需要记住尾调用的返回位置，而是带着返回值直接从被调函数越级跳转到调用函数的返回位置，相当于连续返回了两次，减少了栈中一次调用帧的存取，如图1所示。

由于尾调用是外层函数的最后一步操作，尾调用返回后，外层函数也就返回了。执行尾调用的时候，外层函数栈帧中保存的调用位置、内部变量等信息都不会再用到了，所以，可以用内层函数（即尾调用函数）的栈帧覆盖外层函数的栈帧（而不是在外层函数栈帧下面再新开一个），这样可以节省栈空间。

如果觉得有些抽象，可以举个具体例子：

很明显的，调用g（3）之后，函数f（）就结束了，所以当执行到g（3）的时候，完全可以用g（3）的栈帧覆盖f（）的栈帧。

从原理上我们发现，尾调用的栈是易于优化的。无论有多少层尾调用，都可以通过消除保持栈中的调用帧始终只有一条，从而减少内存使用，提高运行速度。在图2中，func0和func1的局部变量、func1和func2的返回位置等数据都变为了无用，于是可依次用func1和func2的栈帧迭代覆盖掉func0的栈帧，而不是在func0、func1或func2栈帧外再新开一个。尾调用优化（Tail Call Optimization， TCO）或尾调用消除（Tail Call Elimination）让尾位置的函数返回跟goto语句的执行效率一样高，在汇编层面成功地用jmp替代了call的职能。理论上讲尾调用可以通过简化函数调用栈的结构获得性能提升，但实际上尾调用消除是否能真正起作用决定于运行环境是否支持此类优化，以及编程时是否开启这两方面的因素。

尾调用优化是从ES6才开始出现的概念，以JavaScript为例，尾调用优化只有在严格模式（strict mode）下才有效，在正常模式下是无效的。该模式是ECMA-262规范定义的JavaScript标准，其开启命令"use strict"在 JavaScript 1.8.5 （ECMA Script5） 中增加，發布于2009年12月。表达式"use strict"的声明必须在脚本或函数的开头添加。它不是一条语句，而是一个字符串字面量，在 JavaScript 旧版本中会被忽略。目前主流浏览器都已支持严格模式，如：Internet Explorer 10 +、Firefox 4+、Chrome 13+、Safari 5.1+、Opera 12+、IOS 5+、Android 3+等①。在严格模式下，存在诸如：不允许使用未声明的变量，不允许删除变量或对象，不允许删除函数等限制，需要注意。

如果是用GCC编译的话，加上-O2或-O3的优化参数就可以轻松识别尾调用了;VC也有类似选项。不过值得指出的是，在C++、C#等语言的函数体中若存在结构体或类的构造，那么在调用结束返回时，由编译器自动生成的析构函数很可能会取代return语句的末尾位置，隐式的变为调用函数的“最后一个动作”，依据定义判断这就不是尾调用了。为了解决这一问题，C++引入了一项编译优化技术，叫作“返回值优化”（Return Value Optimization， RVO）。基本手段是将待返回的对象构造在调用者的栈帧上，这样调用者就可以直接访问这个对象而不必复制了，自然也省去了调用析构函数。可以认为是强制开启了尾调用优化。

一般来说，尾调用消除是可选的，可以用，也可以不用。但是，在函数式编程语言中，语言标准通常会要求编译器或运行平台实现尾调用消除，让程序员可以用递归代替循环而不丧失性能。尾递归的优化效果最为明显，尤其是递归算法非常复杂的情形。

在尾调用中有一种特殊但重要的情况叫作尾递归。一般地，函数调用自身，称为递归。如果是尾调用自身，就称为尾递归。我们知道，递归作为一种解决复杂问题的方法思路，有时候比迭代更具有可读性和可维护性，但不得不考虑栈资源的耗费;由于需要同时保存所有中间函数的调用帧，容易因压栈过深带来性能下降，更面临着“栈溢出”（stack overflow）错误的风险。尾递归很好地解决了这一矛盾——由于只存在一個调用帧，所以永远不会发生“栈溢出”的错误。以累加求和为例，f（n） = f（n-1） + n; 会保存n个调用帧，而使用尾递归f（n， sum） = f（n-1， sum+n）; 则只需保留最后一个栈帧即可，前面的都可以删掉，这样复杂度也从O（n）降到了O（1）。经过适当处理，尾递归形式的函数的运行效率可以得到极大优化，达到与循环相当的水平。以斐波那契数列（Fibonacci）为例：

我们发现，尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。要做到这一点，就须把所有用到的内部变量改写成函数的参数。这样做看起来不大直观，解决办法有两种：

方法1：在尾递归函数之外，再提供一个正常形式的函数。

方法2：函数式编程里有个术语叫作currying，音译为“柯里化”，意思是将接收多参数的函数表面上转换成只接收单参数函数的形式，实际上是返回一个用来接收余下参数的新函数的技术。听起来有点绕，下面看看具体实例。

curry，其实就是我们所熟知的“咖喱”;currying，意为烹制咖喱菜。特点是把许多种香料（如：姜黄，胡荽籽，辣椒，孜然，小茴香，白胡椒，花椒，芥末等）分别准备好后，放在一起煮，合成一道菜，有点像“八宝粥”的意思。用其命名，十分形象。在上例中Fibonacci传递n，currying调用tailFibonacci、传递 1， 1，最后合在一起。“柯里化”在本质上就是一个分步处理参数的过程，可以使函数更具可读性和弹性。见下：

前面我们已经知道了如何将非尾递归函数改写为尾递归的形式，以便使用尾调用优化。进一步的，我们来了解一下这样的尾递归优化在计算机系统中是如何实现的，这有利于我们在一些无法使用尾调用优化的情况下（如：ES5环境或程序不符合尾调用范式）手动产生那样的效果。

下述tail函数的精妙之处在于状态变量active的运用。默认情况下，该变量是不激活的;而一旦进入尾递归优化的过程，这个变量就激活了。在上例的第一次调用后，变量active会被“激活”。于是后续每次递归，都只是将本次接收的参数推入stack数组，直接返回不进入下一轮递归;而返回后由于stack数组里有一个数组项，通过while循环又处理新的参数列表，所以就会一直重复“进入递归->获得参数列表->返回->进入递归->...”这样的轮回，直到某次递归没有向stack数组推入新的参数为止。如此一来就很巧妙地将“递归”改写成了“循环”，后一轮的参数会取代前一轮的参数，保证调用栈永远只有一层。

补充一点说明，虽然在此我们多用JS举例，但对于C++等编程语言也完全适用。

综上所述我们看到，尾递归由于可通过“尾调用消除”技术予以简化，从而具有不同于一般递归的重要性。本文系统阐述了尾递归的优化原理、使用方法和构造技巧，熟练掌握并灵活运用将会给编程爱好者带来不小的启发和帮助。

注释：

① 引自网站”Can I use... Support tables for HTML5， CSS3， etc，https：//caniuse.com/#feat=use-strict.

参考文献：

[1] 方悦. 循环、迭代与递归[J]. 电脑知识与技术， 2020， 16（6）： 55-57， 66.

[2] 阮一峰. ECMAScript 6 入门[M]. 北京： 电子工业出版社， 2014.

[3] 崔蕊. 递归到非递归算法的转换[J]. 电脑知识与技术， 2009， 5（23）： 6424-6425， 6458.

[4] 张国. 基于递归算法的非递归实现研究[J]. 长江大学学报（自然科学版）理工卷， 2009， 6（3）： 223-225.

[5] 高汉平， 方志雄. 从递归算法到非递归的变换[J]. 黄冈师范学院学报， 2002， 22（3）： 47-50.

【通联编辑：谢媛媛】