Haskell/递归

递归 (解决方案)

基础 Haskell

递归
 列表 II (map)
列表 III (folds, comprehensions)
类型声明
 模式匹配
 控制结构
 关于函数的更多信息
 高阶函数
 有效使用 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 加 4 次。当然，将 5 加 4 次与将 5 加 3 次，然后再加上一个 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的备用版本一样。