Haskell/递归

递归 (解决方案)

基础 Haskell

递归
 列表 II (map)
列表 III (折叠，推导)
类型声明
 模式匹配
 控制结构
 更多关于函数
 高阶函数
 有效使用 GHCi

编辑本章节

递归函数在 Haskell 中起着核心作用，并且通常在计算机科学和数学中被广泛使用。递归本质上是一种重复形式，我们可以通过区分函数含义是递归的，以及它表现的方式来理解它。

递归函数意味着：一个函数可以调用自身。

它的行为是这样的：它仅在满足条件时调用自身，就像 if/else/then 表达式一样，或者像一个模式匹配，其中包含至少一个基本情况来终止递归，以及一个递归情况，导致函数调用自身，从而创建一个循环。

如果没有终止条件，递归函数可能会永远循环，导致无限循环。

数字递归

阶乘函数

数学（特别是组合学）有一个叫做阶乘的函数。^[1] 它以一个非负整数作为参数，找到所有小于或等于“n”的正整数，并将它们全部相乘。例如，6 的阶乘（表示为 $6!$ ）是 $1\times 2\times 3\times 4\times 5\times 6=720$ 。我们可以使用递归风格在 Haskell 中定义它

让我们看看两个相邻数字的阶乘

示例：连续数字的阶乘

Factorial of 6 = 6 × 5 × 4 × 3 × 2 × 1
Factorial of 5 =     5 × 4 × 3 × 2 × 1

注意我们是如何对齐的。你可以在这里看到 $6!$ 包含 $5!$ 。事实上， $6!$ 仅仅是 $6\times 5!$ 。让我们继续

示例：连续数字的阶乘

Factorial of 4 = 4 × 3 × 2 × 1
Factorial of 3 =     3 × 2 × 1
Factorial of 2 =         2 × 1
Factorial of 1 =             1

任何数字的阶乘就是该数字乘以比它小 1 的数字的阶乘。有一个例外：如果我们要求 0 的阶乘，我们不希望将 0 乘以 -1 的阶乘（阶乘只适用于正数）。事实上，我们只是说 0 的阶乘是 1（我们定义它是这样的。只需相信我们，这是正确的。^[2]）。因此，0 是递归的基本情况：当我们到达 0 时，我们可以立即说答案是 1，不需要递归。我们可以总结阶乘函数的定义如下

0 的阶乘是 1。
任何其他数字的阶乘就是该数字乘以比它小 1 的数字的阶乘。

我们可以直接将它翻译成 Haskell

示例：阶乘函数

factorial 0 = 1
factorial n = n * factorial (n - 1)

这定义了一个名为 factorial 的新函数。第一行说 0 的阶乘是 1，第二行说任何其他数字 n 的阶乘等于 n 乘以 n - 1 的阶乘。注意 n - 1 周围的括号；如果没有它们，这将被解析为 (factorial n) - 1；请记住，函数应用（将函数应用于值）在没有显式分组的情况下优先于其他任何操作（我们说函数应用比其他任何操作绑定更紧密）。

注意

上面的 factorial 函数最好定义在一个文件中，但由于它是一个小函数，在 GHCi 中将其写成单行是可行的。为此，我们需要添加一个分号来分隔行

    > let factorial 0 = 1; factorial n = n * factorial (n - 1)

Haskell 实际上使用行分隔和其他空格来代替分号和括号等分隔符。Haskell 程序员通常更喜欢单独的行和适当缩进的简洁外观；尽管如此，显式使用分号和其他标记始终是一个替代方案。

上面的示例演示了数字 n 的阶乘与比它略小的数字 n - 1 的阶乘之间的简单关系。

将函数调用视为委托。递归函数的指令委托了一个子任务。碰巧的是，委托函数使用与委托者相同的指令；只是输入数据发生了变化。递归函数唯一真正令人困惑的地方是每个函数调用都使用相同的参数名称，因此跟踪多个委托可能很棘手。

让我们看看执行 factorial 3 时会发生什么

3 不等于 0，因此我们计算 2 的阶乘
- 2 不等于 0，因此我们计算 1 的阶乘
  - 1 不等于 0，因此我们计算 0 的阶乘
    - 0 等于 0，因此我们返回 1。
  - 为了完成对 1 的阶乘的计算，我们将当前数字 1 乘以 0 的阶乘，即 1，得到 1（1 × 1）。
- 为了完成对 2 的阶乘的计算，我们将当前数字 2 乘以 1 的阶乘，即 1，得到 2（2 × 1 × 1）。
为了完成对 3 的阶乘的计算，我们将当前数字 3 乘以 2 的阶乘，即 2，得到 6（3 × 2 × 1 × 1）。

（注意我们最终得到了两次出现的 1，因为基本情况是 0 而不是 1；但这没关系，因为乘以 1 不会有任何影响。如果我们想的话，我们可以设计 factorial 在 1 处停止，但约定（通常很有用）是定义 0 的阶乘。）

在阅读或编写递归函数时，你很少需要逐个“展开”递归——我们将此留给编译器。

关于我们对 factorial 的递归定义，还有一点需要注意：两个声明（一个是 factorial 0，一个是 factorial n）的顺序很重要。Haskell 通过从顶部开始并选择第一个匹配的函数定义来决定使用哪个函数定义。如果我们在“基本情况”（factorial 0）之前放置了通用情况（factorial n），那么通用的 n 将匹配传递给它的任何内容——包括 0。然后编译器将得出结论，factorial 0 等于 0 * factorial (-1)，依此类推，直到负无穷大（显然这不是我们想要的）。因此，始终从最具体的开始，依次到最通用的列出多个函数定义。

练习

将阶乘函数输入到 Haskell 源文件中，并将其加载到 GHCi 中。
尝试诸如 factorial 5 和 factorial 1000 之类的示例。^[3]
- factorial (-1) 怎么样？为什么会出现这种情况？
一个数 n 的双阶乘是所有从 1 到 n 的与 n 奇偶性相同的整数的乘积。例如，8 的双阶乘是 8 × 6 × 4 × 2 = 384，而 7 的双阶乘是 7 × 5 × 3 × 1 = 105。在 Haskell 中定义一个doubleFactorial函数。

循环、递归和累积参数

命令式语言在 Haskell 程序使用递归的相同上下文中使用循环。例如，在 C（一种典型的命令式语言）中编写阶乘函数的一种惯用方法是使用for循环，如下所示

示例：命令式语言中的阶乘函数

int factorial(int n) {
  int res = 1;
  for ( ; n > 1; n--)
    res *= n;
  return res;
}

在这里，for 循环导致res反复乘以n。每次重复后，n会减去1（这就是n--的作用）。当n不再大于1时，重复停止。

将这样的函数直接翻译成 Haskell 是不可能的，因为不允许更改变量res和n的值（破坏性更新）。但是，您可以始终通过将每个循环变量作为递归函数的参数来将循环转换为等效的递归形式。例如，以下是将上述循环递归“翻译”成 Haskell 的示例

示例：使用递归模拟循环

factorial n = go n 1
    where
    go n res
        | n > 1     = go (n - 1) (res * n)
        | otherwise = res

go是一个辅助函数，它实际执行阶乘计算。它接受一个额外的参数res，该参数用作累积参数来构建最终结果。

注意

根据您熟悉的语言，您可能对递归引起的性能问题感到担忧。但是，Haskell 和其他函数式编程语言的编译器包含许多针对递归的优化（鉴于递归的频繁使用，这并不奇怪）。此外，Haskell 是惰性的——计算仅在其他计算需要其结果时执行，这有助于避免某些性能问题。我们将在后面的章节中进一步讨论这些问题以及它们涉及的一些微妙之处。

其他递归函数

事实证明，factorial函数并没有什么特别之处；许多数值函数都可以用自然的方式递归定义。例如，让我们考虑一下乘法。当您第一次学习乘法时（还记得那个时刻吗？:)), 它可能是通过“重复加法”的过程实现的。也就是说，5 × 4 与将 5 相加四次的结果相同。当然，将 5 相加四次与将 5 相加三次然后再加上一次是相同的，即 5 × 4 = 5 × 3 + 5。这导致了乘法的自然递归定义

示例：递归定义的乘法

mult _ 0 = 0                      -- anything times 0 is zero
mult n m = (mult n (m - 1)) + n   -- recurse: multiply by one less, and add an extra copy

退一步，我们可以看到数值递归如何适应一般的递归模式。数值递归的基线通常由一个或多个特定数字（通常为 0 或 1）组成，这些数字可以立即给出答案。递归情况通过递归调用该函数并使用较小的参数，并使用结果以某种方式生成最终答案来计算结果。使用的“较小参数”通常比当前参数少 1，导致递归“沿着数轴向下行走”（如上面factorial和mult的示例）。但是，原型模式不是唯一的可能性；较小的参数也可以通过其他方式生成。

练习

类似于上面我们对factorial 3的展开，展开乘法 5 × 4。
定义一个递归函数power，使得power x y将x提升到y次方。
您得到一个函数plusOne x = x + 1。在不使用任何其他(+)的情况下，定义一个递归函数addition，使得addition x y将x和y加在一起。
（更难）实现log2函数，该函数计算其参数的整数对数（以 2 为底）。也就是说，log2计算小于或等于其参数的 2 的最大次方的指数。例如，log2 16 = 4，log2 11 = 3，log2 1 = 0。（一个小提示：阅读紧接这些练习之前的那一段文字的最后一句话。）

基于列表的递归

Haskell 有很多递归函数，特别是与列表相关的函数。^[4] 考虑一下length函数，它用于查找列表的长度

示例：length的递归定义

length :: [a] -> Int
length []     = 0
length (x:xs) = 1 + length xs

注意

如果您尝试从源文件加载上面的定义，当您尝试使用它时，GHCi 会抱怨“歧义出现”，因为 Prelude 已经提供了length。在这种情况下，只需将您正在定义的函数的名称更改为其他名称，例如length'或myLength。

因此，length的类型签名告诉我们它接受任何类型的列表并生成一个Int。下一行说空列表的长度为 0（这是基线）。最后一行是递归情况：如果一个列表不为空，那么它可以分解为第一个元素（这里称为x）和列表的其余部分（如果不再有元素，它将只是空列表），按照惯例，它将被称作xs（即x的复数）。列表的长度是 1（考虑x）加上xs的长度（如下一步中的tail示例，当参数列表与 (:) 模式匹配时，xs被设置）。

考虑一下连接函数(++)，它将两个列表连接在一起

示例：递归的(++)

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
Prelude> "Hello " ++ "world" -- Strings are lists of Chars
"Hello world"

(++) :: [a] -> [a] -> [a]
[] ++ ys     = ys
(x:xs) ++ ys = x : xs ++ ys

这比length复杂一些。类型说(++)接受两个相同类型的列表并生成另一个相同类型的列表。基线说将空列表与列表ys连接与ys本身相同。最后，递归情况将第一个列表分解为其头部（x）和尾部（xs），并说要连接两个列表，将第一个列表的尾部与第二个列表连接起来，然后将头部x连接到前面。

这里有一个模式：对于基于列表的函数，基线通常涉及一个空列表，递归情况涉及将列表的尾部再次传递给我们的函数，以便列表逐渐变小。

练习

为以下基于列表的函数给出递归定义。在每种情况下，想想基线是什么，然后思考一般情况是什么，以所有比它小的东西为例。（请注意，所有这些函数都可以在 Prelude 中使用，因此在 GHCi 中测试您的定义时，您需要为它们取不同的名称。）

replicate :: Int -> a -> [a]，它接受一个计数和一个元素，并返回该元素重复该次数的列表。例如，replicate 3 'a' = "aaa"。（提示：考虑计数为 0 的任何元素的复制应该是什么；计数为 0 是您的“基线”。）
(!!) :: [a] -> Int -> a，它返回给定“索引”处的元素。第一个元素在索引 0 处，第二个元素在索引 1 处，依此类推。请注意，对于此函数，您正在进行数值递归和向下列表递归^[5]。
（有点难。）zip :: [a] -> [b] -> [(a, b)]，它接受两个列表并将它们“压缩”在一起，以便结果列表中的第一对是两个列表的前两个元素，依此类推。例如，zip [1,2,3] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')]。如果两个列表中的任何一个比另一个列表短，您可以在任何一个列表用完时停止。例如，zip [1,2] "abc" = [(1, 'a'), (2, 'b')]。
使用辅助函数和累积参数定义length，就像循环式替代版本的factorial一样。