递归 属于

关于 递归

递归函数是调用自身的函数。

递归函数至少需要一个_基本情况_和一个_递归情况_。

基本情况返回一个值，而不再调用函数。递归情况再次调用函数，并修改输入，使其最终能够匹配基本情况。

通常，每种情况都写在各自的函数子句中。

# base case
def count([]), do: 0

# recursive case
def count([_head | tail]), do: 1 + count(tail)

递归函数可以有多个基本情况和/或多个递归情况。例如，斐波那契数列 就是一个有两个基本情况的递归数列：

def fibonacci(0), do: 0
def fibonacci(1), do: 1
def fibonacci(n), do: fibonacci(n - 1) + fibonacci(n - 2)

计算给定值x在数组中出现的次数有两个递归情况：

def count_occurrences([], _x), do: 0
def count_occurrences([x | tail], x), do: 1 + count_occurrences(tail, x)
def count_occurrences([_ | tail], x), do: count_occurrences(tail, x)

通过递归实现循环

由于不可变性，Elixir 中的循环写法与命令式语言不同。例如，循环通常看起来像这样：

for(i = 0; i < array.size; i++) {
  # do something with array[i]
}

在函数式语言中，无法修改i（通过调用i++）。因此，循环必须用递归来实现。

在 Elixir 中，for循环的等价写法如下：

def loop([]), do: nil

def loop([head | tail]) do
  do_something(head)
  loop(tail)
end

在实践中，遍历数组和其他可枚举数据结构最常使用 Enum 模块。在底层，Enum模块中的函数是使用递归实现的。

无限执行

如果实现不当，递归函数可能永远不会返回结果。这可能会造成问题，因为每次调用函数时，都会在内存中存储一个引用，指向虚拟机应返回结果的位置（在调用栈上）。如果递归函数无限地调用自身，可能会耗尽内存，导致虚拟机崩溃（栈溢出错误）。Elixir 运行的 Erlang 虚拟机专门针对递归和可靠性进行了优化，因此可能需要很长时间才会显现无限递归错误或发生崩溃。

这种无限执行的问题可能由以下原因引起：

• 忘记实现基本情况。
• 没有将基本情况定义为第一个子句。
• 在进行递归调用时没有正确修改实参，从而永远无法到达基本情况。