递归

  1. 1. 递归中的环
  2. 2. 归约和映射算法

递归中的环

由于恒定性,Elixir中的环(与其他函数式编程语言一样)和命令式语言中的写法是不同的。例如,C语言中的写法是这样的:

  1. for(i = 0; i < sizeof(array); i++) {
  2. array[i] = array[i] * 2;
  3. }

上述例子中,我们更改了数组和变量i。在Elixir中是不可更改的。所以函数式语言中以递归来替代:一个函数被反复调用,直到情况达到停止条件。在这个进程中没有数据被改变。思考下面的例子,一个字符串被打印任意次:

  1. defmodule Recursion do
  2. def print_multiple_times(msg, n) when n <= 1 do
  3. IO.puts msg
  4. end
  5. def print_multiple_times(msg, n) do
  6. IO.puts msg
  7. print_multiple_times(msg, n - 1)
  8. end
  9. end
  10. Recursion.print_multiple_times("Hello!", 3)
  11. # Hello!
  12. # Hello!
  13. # Hello!

case类似,一个函数可以拥有许多从句。当传递来的参数与从句的参数模式相匹配并且其卫语句返回值为真,那么特定的从句就会被执行。

在上述例子中,当第一次调用print_multiple_times/2时,变量n等于3

第一个从句的守卫说道“当且仅当n小于或等于1时使用这个定义”。由于不符合这个情形,Elixir继续到下一个从句定义。

第二个定义匹配模式成功,并且没有守卫,所以被执行了。它先打印了我们的msg然后调用了他自己并传递了参数n-1 (2)

我们的msg再次被打印,print_multiple_times/2也再次被调用,这一次第二个参数被设置成了1。由于n已经被设置成1了,print_multiple_times/2的第一个定义中的卫语句执行结果为真,所以我们执行了这个定义。msg被打印同时没有额外的语句需要执行了。

我们这样定义print_multiple_times/2,无论第二个参数是什么数字,它不是触发了我们的第一个定义(被称为基本案例),就是触发了我们的第二个定义,并向基本案例更近了一步。

归约和映射算法

让我们看看如何利用递归的力量来计算一个列表的数字之和:

  1. defmodule Math do
  2. def sum_list([head | tail], accumulator) do
  3. sum_list(tail, head + accumulator)
  4. end
  5. def sum_list([], accumulator) do
  6. accumulator
  7. end
  8. end
  9. IO.puts Math.sum_list([1, 2, 3], 0) #=> 6

我们以列表[1, 2, 3]和初始值0为参数调用了sum_list。我们将逐个尝试从句,直到模式匹配成功。这个案例中,列表[1 ,2, 3]匹配了[head | tail]head对应着1tail对应着[2, 3]accumulator设置成0

接着,我们将列表的头与收集器相加head + accumulator,并将列表的尾作为第一个参数再次调用sum_list。尾会再次匹配[head | tail]直到列表变空:

  1. sum_list [1, 2, 3], 0
  2. sum_list [2, 3], 1
  3. sum_list [3], 3
  4. sum_list [], 6

当列表为空时,将匹配最后的从句,返回最终结果6

将一个列表归约成一个值的过程叫做归约算法,它是函数式编程的中心。

如果我们想将列表中所有值翻倍呢?

  1. defmodule Math do
  2. def double_each([head | tail]) do
  3. [head * 2 | double_each(tail)]
  4. end
  5. def double_each([]) do
  6. []
  7. end
  8. end
  1. iex math.exs
  1. iex> Math.double_each([1, 2, 3]) #=> [2, 4, 6]

这里我们使用递归来遍历列表,将每个元素翻倍并返回一个新的列表。将一个列表映射到一个新列表的过程叫做映射算法。

递归和尾调用是Elixir中的重要部分,且常用于创建环。然而在实际使用Elixir时,你很少会像上面那样用递归来操作列表。

下一章我们将看到的Enum模块,已经提供了许多用于操作列表的便捷方法。实际中,上述例子可以写成:

  1. iex> Enum.reduce([1, 2, 3], 0, fn(x, acc) -> x + acc end)
  2. 6
  3. iex> Enum.map([1, 2, 3], fn(x) -> x * 2 end)
  4. [2, 4, 6]

或者使用捕获语法:

  1. iex> Enum.reduce([1, 2, 3], 0, &+/2)
  2. 6
  3. iex> Enum.map([1, 2, 3], &(&1 * 2))
  4. [2, 4, 6]

让我们进一步观察Enumerable以及它懒惰的相对物Stream