函数式编程中的尾调用

每次调用函数都会消耗内存。通常我们不需要担心，今天的计算机有足够的内存，而且Erlang VM在保持较低计算成本方面做得很好。但如果执行数百万次递归调用，仍然会消耗大量内存。本节将讨论降低递归函数消耗内存的方法。我们将充分利用编译器的尾调用优化。

尾调用优化是指编译器减少内存中的函数数量。它是函数式编程语言常见的编译器功能。要利用它，必须确保函数的最后一个表达式是一个函数调用。如果最后一个表达式是一个新函数调用，那么当前函数的返回值就是新调用函数的返回值，也就不需要将当前函数保留在内存中。考虑下面这个例子：

调用scream.（"help"）时，程序会将它放入内存栈然后执行函数体。scream函数将传递单词help，并得到"HELP！！！"。最后一个表达式将引发函数调用：String.upcase（"help！！！"）。scream.（"help"）的结果与String.upcase（"help！！！"）相同。所以，程序将从函数调用堆栈中删除scream.（"help"），从而优化内存。

让我们再看看阶乘模块的递归部分：

最后一行有一个递归调用，但最后一个表达式是对＊运算符的调用。Elixir将执行of（n - 1）调用，并将其结果乘以n。这个函数是体递归函数，它的最后一个表达式不是递归调用，所以无法利用尾调用优化。我将使用一个大数字来生成数百万个递归调用。读者可以用进程监视器查看它对内存的巨大影响，请准备好终止程序。在IEx中试一试：

这是我做这个实验时的测试结果（见图4-1）：

图4-1　体递归函数消耗内存的情况

你在自己计算机上看到的内存消耗数字可能会不同，但也非常高。执行重复性任务需要大量内存。不过，我们可以将该函数转换为尾递归函数。

创建尾递归函数的常用方法是将函数结果替换为累积每次迭代结果的额外参数。让我们创建一个尾递归版本的Factorial模块，并将其与之前的版本进行比较。创建一个名为TRFactorial的模块：

我们创建了一个辅助函数factorial_of，它有一个额外的参数，用于累积乘法运算。参数acc是上一次迭代的结果。进行递归调用时，使用表达式acc ＊n传递结果。最后一个表达式是递归调用，而不是对＊运算符的调用。新的函数是尾递归的，编译器可以对它进行优化。再测试新模块的内存消耗情况。请准备好终止程序，因为即使进行内存优化，也需要很长时间才能完成。

这是我的测试结果（见图4-2）：(www.xing528.com)

图4-2　尾递归函数消耗内存的情况

新模块对内存的消耗大大降低了！但是我们的代码也变得更复杂了。在决定用体递归（body-recursive）函数还是尾递归（tail-recursive）函数前，有必要权衡利弊。一般来说，如果程序要迭代数百万次，而且尾递归函数不难读懂和维护，那么请使用尾递归。如果迭代次数很少，而且尾递归函数难以理解和维护，那么请使用体递归。