Haskell/递归

递归 (解答)

Elementary Haskell

递归这个绝妙想法是Haskell（一般也是计算机科学）的中心：即，递归是在一个函数定义的内部用到自身。有此种定义的函数叫做递归。听起来好像会导致无限重复，但只要定义适当，就不会这样。

一般来说，一个递归函数的定义有两个部分。首先，至少要有一个底线，就是一个简单的线，越过此处，递归会停止（换言之，此时函数会直接返回值，而不会继续“递归般地”调用自身。底线保证了此函数必定结束。其次，是更一般的递归区，若参数在此范围内就会以某种形式调用自身。下面是例子。

数值递归

阶乘函数

数学上，尤其是组合数学，有一个相当常用的函数叫做阶乘(Factorial)。^[1]阶乘函数的参数是一个自然数，它会返回1与此数之间所有数的乘积。比如，6的阶乘是 1 × 2 × 3 × 4 × 5 × 6 = 720 。这相当有趣，因为对我们来说，它可以用一种递归函数来表示。

首先，我们比较相邻两个数的阶乘。

Example

例子: 相邻数的阶乘

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

注意我们是如何对齐的。明显可以看出6的阶乘和5的阶乘有关系。6的阶乘就是6 × （5的阶乘）。让我们来看另一个例子。

Example

例子: Factorials of adjacent numbers

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
任何数的阶乘都是此数乘以比此数小一的数的阶乘。

这个在Haskell中表示为：

Example

例子: 阶乘函数

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

这就定义了一个新的叫做factorial的函数。第一行表示0的阶乘是1，第二行表示任意别的数n的阶乘等于n乘以 n-1的阶乘。注意那个把n-1括起来的括弧：没有这个括弧代码就会被解析称为(factorial n) - 1；函数行为的优先级是很高的，会最先执行。 Template:Warning

到现在为止，你都会觉得有点微妙。实际上起作用吗？来看看到底执行了factorial 3到底会发生什么事情吧：

3不是0，所以“递归”（再次执行factorial函数）：看2的阶乘是几（也就是factorial 3）
- 2不是0，所以“递归”
  - 1不是0，递归
    - 0就是0，所以我们返回1
  - 我们将得到的1和本来的1相乘，得到 1 ，即(1 × 1)，返回它
- 我们将得到的1和本来的2相乘，得到2，即(2 × 1 × 1)，返回它
我们将得到的2和本来的3相乘，得到6，即6 (3 × 2 × 1 × 1)

我们可以看出乘法如何贯穿整个递归过程。

注意，我们最终的式子中1出现了两次，因为底线是0而不是1；不过这造不成什么错误，因为乘1还会是原来的数。如果我们想让 factorial 在1处停下也办得到，但0做底线符合常理，而且会很实用。

还有一点需要注意的：两个声明（一个是factorial 0的声明，一个是factorial n的声明）的顺序很重要。Haskell会先匹配第一个句子，来决定函数的定义。所以，如果我们把两句声明掉个，第一个n语句将会匹配任何数（包括0）。所以语句 factorial 0的执行过程是去匹配情况n，于是factorial 0 的结果将会是0 * factorial (-1)，然后就会没完没了。无限循环不是我们想要的。一般来说：特殊情况应该置于前，一般情况置于后。

练习

将阶乘函数键入到一个源文件中，再载入到你的Haskell环境中
- factorial 5是几?
- 那 factorial 1000呢?如果你有个计算器，先用它算一算，然后看看和电脑中的一样吗？
- 要是 factorial (-1)会如何？为何如此？
双阶乘意为：从1（或2）隔一个数字乘一个，一直乘到n。比如，8的双阶乘是 8 × 6 × 4 × 2 = 384, 7的双阶乘是 7 × 5 × 3 × 1 = 105. 定义一个双阶乘函数doublefactorial.

一次小小的跑题

此段落欲为习惯命令式语言如c或Java的用户提供指导。

在命令式语言中，“循环”是很普遍的。在命令式语言中，阶乘函数的通常写法是用一个“for”循环，如下（用c语言）：

Example

例子: 命令式语言中的阶乘函数

int factorial(int n) {
  int res = 1;
  for (i = 1; i <= n; i++)
    res *= i;
  return res;
}

这在Haskell中直接实现是不可能的，因为改变变量res和i的值（以一种破坏性的方式）是不可以的。然而，我们依然可以将一个循环转换为同作用的递归形式。重点是让每个需要改变的循环变量变成一个递归函数的参数。比如，以下将上个循环“直译”为Haskell。

Example

例子: 用递归模拟循环

factorial n = factorialWorker 1 n 1 where
factorialWorker i n res | i <= n    = factorialWorker (i+1) n (res * i)
                        | otherwise = res

垂直号之后的表达式叫做“guards”（卫士），更详细的可以参考control structures。现在，我们应该可以通过与以上的c语言代码相比弄懂它是如何工作的。

很明显，在Haskell中，要实现阶乘函数，这不是一个简明、优雅的方式，但我们应该也知道，这种翻译也可以实现。

另一点需要提醒的是不必担心Haskell中递归性能会很低。一般来说，函数式语言的编译器都会对递归多所优化，包括一个重要的“尾递归优化”；记住：Haskell很懒，如果不必要，就不会发生。

其他递归函数

正如它本身所揭示的，factorial函数没有什么特殊之处；一大批数学函数都可以一种自然地方式递归定义。比如，乘法。你第一次接触乘法（回忆一下那是什么时候？:)），你认为那就是“重复加”而已。就是说， 5 × 4 和加四个5的结果是一样的。当然，加四个5和先加三个5再加一个5是一样的——也就是说， 5 × 4 = 5 × 3 + 5。这让我们自然想到了乘法的递归定义形式。

Example

例子: 递归地定义乘法

mult n 0 = 0                      -- 任何数乘 0 是 0
mult n 1 = n                      -- 任何数乘 1 是它本身
mult n m = (mult n (m - 1)) + n   -- 递归体：乘个数减1再加本身

回头看看，我们可以看到数字递归式如何写成一般递归形式的。数字递归的基线通常包括一个或更多特殊数字（通常是 0 或 1 ），对这些数字，我们可以立刻给出答案。递归体中，通过调用具有更小的参数的函数，相加返回值来产生结果。“更小的参数”通常比本处的参数更小，从而导致递归会“朝着更小的数走去”（就像factorial的例子一样）。当然，更小的参数也可以由其他方式产生。

练习

展开 5 × 4 ，方式参考 factorial 3的展开。
定义一个递归函数 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中“很多”函数都是递归函数，尤其是跟表有关的。^[3]设想一个可以计算表长度的 length 函数。

Example

例子: length的递归定义

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

别被眼花缭乱的语法弄蒙了，我们会在模式匹配章节更深入的了解。现在，我们把代码翻译成人话，搞懂它如何发挥作用。第一行说明了 length的类型：它允许任何表进去，并且产生一个 Int，也就是整数。下一行表示一个空表的长度是 0 。当然，这也是基线（底线）。最后一行是递归区：如果一个表包括一个第一元素 x 和表的其余部分、另外一个表 xs ，那么表的长度是 xs 的长度加1。

那么一个 (++) 函数，这个函数可以实现两个表相连，该如何实现呢？（下面给出这个运算符的几个例子，因为我们还没见到过这个功能呢。）

{{HaskellExample|<递归的code>(++)函数|

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 订在前面。

这就是模式：在基于表的函数中，基线通常和空表相关，递归区通常会把表的尾部再传回函数自身以递归，这样表会越来越小。

练习

给出以下基于表的函数的递归定义。对每一题，想想基线是什么，而递归区又如何，又如何做到参数越来越小？

replicat :: Int -> a -> [a]，作用是接受一个数字和一个元素，返回有此数字个元素的表。比如： replicat 3 'a' = "aaa" 。（提示：考虑下0个元素的表是什么样子，个数 0 就是你的基线。
(!!) :: [a] -> Int -> a在给出的 index（指针）处返回元素。第一个元素是 index 0第二个是 1 ，以此类推。注意在此函数中，你得对数字和表同时“递归”。
（有点难度） zip :: [a] -> [b] -> [(a, b)] ，拉链函数，将每个表中对应位置的元素连在一起，组成一个大表。比如 zip [1,2,3] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')] 。如果某个表比较短，则立即停止即可。如 zip [1,2] "abc" = [(1, 'a'), (2, 'b')] 。

递归几乎是所有表函数和数字函数的实现方法。下一次你再遇到基于表的函数时，先看看空表时的情况，再看看不空时的情况，也就知道这个算法是不是递归的了。呵呵。