Elixir递归 #

一、递归基础 #

1.1 什么是递归 #

递归是函数调用自身的编程技术。在Elixir中，递归是处理列表和集合的主要方式。

1.2 基本递归 #

elixir

defmodule Recursion do
  def countdown(0), do: IO.puts("Blastoff!")
  def countdown(n) when n > 0 do
    IO.puts(n)
    countdown(n - 1)
  end
end

Recursion.countdown(5)

1.3 递归三要素 #

基本情况：终止递归的条件
递归情况：函数调用自身
收敛性：每次递归都向基本情况靠近

elixir

defmodule Math do
  def factorial(0), do: 1
  def factorial(n) when n > 0, do: n * factorial(n - 1)
end

二、列表递归 #

2.1 列表求和 #

elixir

defmodule MyList do
  def sum([]), do: 0
  def sum([head | tail]), do: head + sum(tail)
end

MyList.sum([1, 2, 3, 4, 5])

2.2 列表长度 #

elixir

defmodule MyList do
  def length([]), do: 0
  def length([_ | tail]), do: 1 + length(tail)
end

MyList.length([1, 2, 3, 4, 5])

2.3 列表映射 #

elixir

defmodule MyList do
  def map([], _func), do: []
  def map([head | tail], func), do: [func.(head) | map(tail, func)]
end

MyList.map([1, 2, 3, 4, 5], fn x -> x * 2 end)

2.4 列表过滤 #

elixir

defmodule MyList do
  def filter([], _pred), do: []
  def filter([head | tail], pred) do
    if pred.(head) do
      [head | filter(tail, pred)]
    else
      filter(tail, pred)
    end
  end
end

MyList.filter([1, 2, 3, 4, 5], fn x -> x > 2 end)

2.5 列表归约 #

elixir

defmodule MyList do
  def reduce([], acc, _func), do: acc
  def reduce([head | tail], acc, func), do: reduce(tail, func.(head, acc), func)
end

MyList.reduce([1, 2, 3, 4, 5], 0, fn x, acc -> acc + x end)

三、尾递归优化 #

3.1 什么是尾递归 #

尾递归是指递归调用是函数的最后一个操作。Erlang VM会优化尾递归，将其转换为迭代，避免栈溢出。

3.2 非尾递归示例 #

elixir

defmodule NonTail do
  def sum([]), do: 0
  def sum([head | tail]), do: head + sum(tail)
end

问题：递归调用后还需要执行加法，不是尾递归。

3.3 尾递归版本 #

elixir

defmodule TailRecursive do
  def sum(list), do: sum(list, 0)

  defp sum([], acc), do: acc
  defp sum([head | tail], acc), do: sum(tail, acc + head)
end

3.4 尾递归反转列表 #

elixir

defmodule MyList do
  def reverse(list), do: reverse(list, [])

  defp reverse([], acc), do: acc
  defp reverse([head | tail], acc), do: reverse(tail, [head | acc])
end

MyList.reverse([1, 2, 3, 4, 5])

3.5 尾递归映射 #

elixir

defmodule MyList do
  def map(list, func), do: map(list, func, []) |> reverse()

  defp map([], _func, acc), do: acc
  defp map([head | tail], func, acc), do: map(tail, func, [func.(head) | acc])
end

四、常见递归模式 #

4.1 斐波那契数列 #

elixir

defmodule Fibonacci do
  def fib(0), do: 0
  def fib(1), do: 1
  def fib(n) when n > 1, do: fib(n - 1) + fib(n - 2)

  def fib_tail(n), do: fib_tail(n, 0, 1)

  defp fib_tail(0, a, _b), do: a
  defp fib_tail(n, a, b), do: fib_tail(n - 1, b, a + b)
end

Fibonacci.fib_tail(50)

4.2 二分查找 #

elixir

defmodule BinarySearch do
  def search(list, target), do: search(list, target, 0, length(list) - 1)

  defp search(_list, _target, low, high) when low > high, do: -1

  defp search(list, target, low, high) do
    mid = div(low + high, 2)
    value = Enum.at(list, mid)

    cond do
      value == target -> mid
      value < target -> search(list, target, mid + 1, high)
      value > target -> search(list, target, low, mid - 1)
    end
  end
end

4.3 快速排序 #

elixir

defmodule QuickSort do
  def sort([]), do: []
  def sort([pivot | tail]) do
    {less, greater} = Enum.split_with(tail, &(&1 < pivot))
    sort(less) ++ [pivot] ++ sort(greater)
  end
end

QuickSort.sort([3, 1, 4, 1, 5, 9, 2, 6])

4.4 归并排序 #

elixir

defmodule MergeSort do
  def sort([]), do: []
  def sort([x]), do: [x]
  def sort(list) do
    {left, right} = Enum.split(list, div(length(list), 2))
    merge(sort(left), sort(right))
  end

  defp merge([], right), do: right
  defp merge(left, []), do: left
  defp merge([l | left], [r | right]) when l <= r do
    [l | merge(left, [r | right])]
  end
  defp merge([l | left], [r | right]) do
    [r | merge([l | left], right)]
  end
end

4.5 树遍历 #

elixir

defmodule Tree do
  defstruct [:value, :left, :right]

  def traverse_preorder(nil), do: []
  def traverse_preorder(%Tree{value: v, left: l, right: r}) do
    [v, traverse_preorder(l), traverse_preorder(r)] |> List.flatten()
  end

  def traverse_inorder(nil), do: []
  def traverse_inorder(%Tree{value: v, left: l, right: r}) do
    [traverse_inorder(l), v, traverse_inorder(r)] |> List.flatten()
  end

  def traverse_postorder(nil), do: []
  def traverse_postorder(%Tree{value: v, left: l, right: r}) do
    [traverse_postorder(l), traverse_postorder(r), v] |> List.flatten()
  end
end

五、递归与迭代 #

5.1 递归方式 #

elixir

defmodule Recursive do
  def sum([]), do: 0
  def sum([head | tail]), do: head + sum(tail)
end

5.2 迭代方式（使用Enum） #

elixir

defmodule Iterative do
  def sum(list), do: Enum.sum(list)
end

5.3 选择建议 #

场景	推荐
简单操作	使用Enum
复杂逻辑	使用递归
性能关键	使用尾递归
学习理解	使用递归

六、递归陷阱 #

6.1 栈溢出 #

非尾递归可能导致栈溢出：

elixir

defmodule Bad do
  def sum([]), do: 0
  def sum([head | tail]), do: head + sum(tail)
end

Bad.sum(1..100_000 |> Enum.to_list())

6.2 无限递归 #

缺少基本情况会导致无限递归：

elixir

defmodule Bad do
  def loop(n), do: loop(n + 1)
end

6.3 不收敛 #

递归不向基本情况靠近：

elixir

defmodule Bad do
  def factorial(n), do: n * factorial(n - 1)
end

七、递归优化技巧 #

7.1 使用累加器 #

elixir

defmodule Optimized do
  def sum(list), do: sum(list, 0)

  defp sum([], acc), do: acc
  defp sum([head | tail], acc), do: sum(tail, acc + head)
end

7.2 使用缓存 #

elixir

defmodule Memoized do
  def fib(n), do: fib(n, %{})

  defp fib(0, _cache), do: 0
  defp fib(1, _cache), do: 1
  defp fib(n, cache) do
    case Map.get(cache, n) do
      nil ->
        result = fib(n - 1, cache) + fib(n - 2, cache)
        {result, Map.put(cache, n, result)}
      cached ->
        cached
    end
  end
end

7.3 使用Stream #

elixir

defmodule StreamExample do
  def fib_stream do
    Stream.unfold({0, 1}, fn {a, b} -> {a, {b, a + b}} end)
  end

  def fib(n) do
    fib_stream() |> Enum.at(n)
  end
end

八、总结 #

本章学习了：

模式	示例
基本递归	`def f(0), do: 1; def f(n), do: n * f(n-1)`
列表递归	`def sum([]), do: 0; def sum([h\|t]), do: h + sum(t)`
尾递归	使用累加器参数
递归优化	尾递归、缓存、Stream