Elixir 中的迭代、递归和尾调用优化
Elixir 使用递归来遍历列表等数据结构。虽然大部分递归都隐藏在类的高级抽象层中Enum，但在某些情况下，自己编写递归函数可能性能更高。在本期 Elixir Alchemy 节目中，我们将尝试找出一些这样的例子。
在此过程中，我们将学习体递归函数和尾递归函数。虽然尾递归函数通常被认为速度更快，但我们也会探讨一些并非总是如此的情况。让我们马上开始吧！
枚举
Elixir 提供了模块函数Enum来枚举集合。
def sum_numbers1(list) do
list
|> Enum.filter(&is_number/1)
|> Enum.reduce(0, fn n, sum -> n + sum end)
end
此示例接受一个列表，并返回该列表中所有数字的总和。由于输入列表中可能包含非数字项，因此它使用 `is` 属性Enum.filter/2仅选择返回 true 的项。is_number/1之后，将剩余的值通过 `$($($($($($($($($($($($($($( ')'))) '') ...））））））））））））））））））））））））））））））））））））Enum.reduce/3
sum_numbers1([1, 2, "three", 4, %{}]) # => 7
虽然这种方法可行，但它需要遍历整个列表两次才能得到结果。为了提高性能，我们可以选择编写一个递归函数，一次性完成所有操作。
递归
递归函数可以一次性完成两项任务（删除非数字项并将剩余项相加）。它会对列表中的每个项调用自身，并使用模式匹配来决定如何处理每个项。
# 1
def sum_numbers2([head | tail]) when is_number(head) do
sum_numbers2(tail) + head
end
# 2
def sum_numbers2([_head | tail]) do
sum_numbers2(tail)
end
# 3
def sum_numbers2([]) do
0
end
该解决方案没有使用模块提供的函数Enum，而是不断调用自身直到列表为空。它使用了三个函数头来实现这一点：
- 当列表的第一个元素（头元素）是一个数字时，我们将调用函数
sum_numbers2/1并传入列表的其余部分（除头元素外的所有元素，称为尾元素）。该函数会返回一个数字，我们将把当前的头元素加到这个数字上。 - 当头部不是数字时，我们将
sum_numbers2/1只使用尾部调用函数来丢弃它。 - 当列表为空时，我们将返回 0。
sum_numbers2([1, 2, "three", 4, %{}]) # => 7
当使用 `--no-return` 调用此函数时[1, 2, "three", 4, %{}]，该sum_numbers2/1函数会按以下顺序重复调用以获得结果：
sum_numbers2([1, 2, "three", 4, %{}])sum_numbers2([2, "three", 4, %{}]) + 1sum_numbers2(["three", 4, %{}]) + 1 + 2sum_numbers2([4, %{}]) + 1 + 2sum_numbers2([%{}]) + 1 + 2 + 4sum_numbers2([]) + 1 + 2 + 40 + 1 + 2 + 4
此列表展示了如何逐步简化函数直至得到结果，结果显示函数被调用了六次：每次调用对应一个元素，最后一次调用则用于空列表。
由于该函数在每次迭代中都会调用自身，因此列表中的每个元素都会导致调用栈中添加一个栈帧。这是因为每个元素都需要调用一个函数，而该函数必须执行才能获取其结果。向调用栈中添加栈帧需要分配一些内存，因此可能会产生一些开销。
尾递归和尾调用优化
为了最大限度地减少内存占用，一些语言（例如 Erlang 和 Elixir）实现了尾调用优化。通过对代码进行少量重写，我们可以阻止栈帧的添加和内存的分配。
# 1
def sum_numbers3(list) do
do_sum_numbers3(list, 0)
end
# 2
defp do_sum_numbers3([head | tail], sum) when is_number(head) do
do_sum_numbers3(tail, sum + head)
end
# 3
defp do_sum_numbers3([_head | tail], sum) do
do_sum_numbers3(tail, sum)
end
# 4
defp do_sum_numbers3([], sum) do
sum
end
这个例子是之前函数的另一种实现方式。不过，这个例子是尾递归的，这意味着它不需要等待自身被调用后再继续执行。它通过维护一个累加器（sum）来保存当前值，而不是堆叠函数调用。
- 该
sum_numbers3/1函数是公共函数，它do_sum_numbers3/2使用传递的列表和一个0初始累加器来调用私有函数。 - 与前面的例子类似，
do_sum_numbers3/2第一个函数 head 用于匹配带有数字头部的列表。它会调用自身，传入列表的尾部，并将头部添加到累加器中。 - 当head不是数字时，第三个函数 head 会通过调用自身并传入tail和当前累加器来丢弃它，而不会改变任何内容。
- 最后，退出子句返回累加器。
通过在函数末尾调用自身并将所有计算值传递给累加器，Erlang 虚拟机可以执行一种称为尾调用优化的技巧，从而避免创建新的栈帧。相反，它通过跳回函数开头来使用当前栈帧。
尾调用优化允许函数调用自身而不会遇到堆栈问题。
def sleep, do: sleep
此示例实现了一个不断调用自身的函数。如果没有尾调用优化，此函数将产生堆栈错误。
哪个更快？
我们为同一个函数编写了三个实现。第一个实现使用 ` Enum.filter/2filter`Enum.reduce/3和 `sum` 函数来过滤和求和列表，并且遍历了列表两次。为了解决这个问题，我们使用了一个递归函数，一次性完成了所有操作，并进一步利用尾调用优化改进了该函数。
letters = Enum.map(?a..?z, fn x -> <<x::utf8>> end)
numbers = Enum.to_list(0..10_000)
list = Enum.shuffle(letters ++ numbers)
Benchee.run(
%{
"Enum.filter/2 and Enum.reduce/3" => fn -> Recursion.sum_numbers1(list) end,
"Body-recursive" => fn -> Recursion.sum_numbers2(list) end,
"Tail-recursive" => fn -> Recursion.sum_numbers3(list) end
},
time: 10,
memory_time: 2
)
为了对我们的解决方案进行基准测试，我们将使用Benchee。我们将为每个函数准备一个打乱顺序的字符串和数字列表，并让它们相加 10 秒钟。
Name ips average deviation median 99th %
Tail-recursive 107.35 K 9.32 μs ±21.39% 9 μs 14 μs
Body-recursive 55.65 K 17.97 μs ±662.77% 14 μs 34 μs
Enum.filter/2 and Enum.reduce/3 20.86 K 47.94 μs ±51.46% 46 μs 85 μs
Comparison:
Tail-recursive 107.35 K
Body-recursive 55.65 K - 1.93x slower
Enum.filter/2 and Enum.reduce/3 20.86 K - 5.15x slower
Memory usage statistics:
Name Memory usage
Tail-recursive 0 B
Body-recursive 0 B
Enum.filter/2 and Enum.reduce/3 16064 B
在这台机器上的测试中，我们发现，使用主体递归的版本速度几乎是使用原始实现的3倍。Enum.filter/2而Enum.reduce/3使用尾递归的版本速度几乎是主体递归版本的2倍。
尾调用递归总是更快吗？
虽然该基准测试的结果看起来相当令人信服，但尾递归并不总是比主体递归更快。事实上，这是Erlang 性能的七大误区之一。
虽然尾递归调用通常对列表归约更快（就像我们之前看到的例子一样），但在某些情况下，主体递归函数可能更快。这在对列表进行映射时尤为常见，因为函数接收一个列表并返回一个列表，而无需将其归约成单个值。
def double_numbers1(list) do
list
|> Enum.filter(&is_number/1)
|> Enum.map(fn n -> n * 2 end)
end
def double_numbers2([]) do
[]
end
def double_numbers2([head | tail]) when is_number(head) do
[head * 2 | double_numbers2(tail)]
end
def double_numbers2([_head | tail]) do
double_numbers2(tail)
end
def double_numbers3(list) do
list
|> do_double_numbers3([])
|> Enum.reverse()
end
defp do_double_numbers3([], acc) do
acc
end
defp do_double_numbers3([head | tail], acc) when is_number(head) do
do_double_numbers3(tail, [head * 2 | acc])
end
defp do_double_numbers3([_head | tail], acc) do
do_double_numbers3(tail, acc)
end
这个例子和我们之前看到的例子很相似，但是这个double_numbers/1函数不是将所有数字相加并简化为一个数字，而是将所有数字翻倍并将它们以列表的形式返回。
和之前一样，我们有三种实现方式。第一种使用Enum.filter/2`and`Enum.map/2循环遍历列表两次，第二种是递归，最后一种是尾递归。尾递归函数在返回之前需要反转列表，因为值会被添加到累加器的前面。
注意：查看示例项目，以比较更多可能的实现方式，例如列表推导式和不反转列表的尾递归版本。
Name ips average deviation median 99th %
body-recursive 36.86 K 27.13 μs ±39.82% 26 μs 47 μs
tail-recursive 27.46 K 36.42 μs ±1176.74% 27 μs 80 μs
Enum.filter/2 and Enum.map/2 12.62 K 79.25 μs ±194.81% 62 μs 186 μs
Comparison:
body-recursive 36.86 K
tail-recursive 27.46 K - 1.34x slower
Enum.filter/2 and Enum.map/2 12.62 K - 2.92x slower
Memory usage statistics:
Name Memory usage
body-recursive 15.64 KB
tail-recursive 20.09 KB - 1.28x memory usage
Enum.filter/2 and Enum.map/2 31.33 KB - 2.00x memory usage
对每种实现方式进行基准测试后，我们可以看到，在这种情况下，主体递归版本速度最快。尾递归版本需要反转列表，这抵消了尾调用优化在这种特定情况下带来的性能提升。
一如既往，这取决于具体情况。
至此，我们对 Elixir 中递归的探讨就结束了。一般来说，尾递归函数如果不需要在返回结果前反转结果，速度会更快。这是因为反转结果需要对整个列表进行另一次迭代。尾递归函数通常在缩减列表时速度更快，就像我们的第一个例子一样。
最佳方法取决于具体情况。对于关键任务循环，编写基准测试来衡量哪种解决方案速度更快通常是最佳选择，因为哪种方案的性能更优并不显而易见。
要了解更多关于递归的知识，也请务必阅读这篇关于可用方法及其适用场景的概述。如果您喜欢这篇文章，请不要忘记订阅邮件列表，以便阅读更多 Elixir Alchemy 的内容！
文章来源：https://dev.to/appsignal/iteration-recursion-and-tail-call-optimization-in-elixir-3ibp