打开主菜单
递归 (解答)

目录

Elementary Haskell

Template:Haskell章节/Elementary Haskell

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

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

数值递归编辑

阶乘函数编辑

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

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

例子: 相邻数的阶乘

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


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

例子: 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中表示为:

例子: 阶乘函数

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),然后就会没完没了。无限循环不是我们想要的。一般来说:特殊情况应该置于前,一般情况置于后。

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

一次小小的跑题编辑

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

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

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

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

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

例子: 用递归模拟循环

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。这让我们自然想到了乘法的递归定义形式。

例子: 递归地定义乘法

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

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

练习
  1. 展开 5 × 4 ,方式参考 factorial 3的展开。
  2. 定义一个递归函数 power ,使得 power x y 计数 xy 次幂。
  3. 已有一个函数 plusOne x = x + 1. 不使用任何 (+)(加号), 定义一个 addition,使得 addition x yxy 相加。
  4. (难) 实现函数 log2, 意思是求以 2 为底的对数。 即, log2 会计算以 2 为底的适合参数的最大的幂。比如, log2 16 = 4log2 11 = 3log2 1 = 0 。(小建议:解题之前,再看一遍最后一段。)


基于表的递归编辑

Haskell中“很多”函数都是递归函数,尤其是跟表有关的。[3]设想一个可以计算表长度的 length 函数。

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

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

练习

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

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

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

不要太爱递归编辑

虽然我们对递归有个牢固的理解很重要,但这并不意味着在Haskell中我们要时时用递归编东西。事实上,有各种各样的用递归函数标准库,你只需要使用它们就可以了。比如,一种实现factorial(阶乘)函数的简单方式是这样的:

例子: 用标准库实现 factorial 函数

factorial n = product [1..n]


简直跟作弊差不多,对吧? :) 这就是有经验的 Haskell 程序员会如何写程序,他们不会动辄祭起递归这个法宝。当然, product 函数的本质就是表递归[4],但当我们用这种方式写代码的时候,不用操心其实现方式了。

概要编辑

递归是一种在函数定义内部调用自身的一种做法。它几乎都是由两种成分构成:基线和递归区。递归在处理表和数字时特别有用。



递归
习题解答
Elementary Haskell

Template:Haskell章节/Elementary Haskell

Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能


库参考 >> 普通实务 >> 特殊任务


注释编辑

  1. 在数学上,n的阶乘用n!表示,但Haskell可没有这种语法,所以这里我们不会这样用。
  2. 事实上,定义0的阶乘是1绝非任意,而是因为0的阶乘代表了 empty product.
  3. 这并非巧合,没有变量,递归是实现控制结构的唯一方法。这听起来很像限制,但只要习惯了,它绝不会碍手碍脚。
  4. 事实上,这个函数叫做 foldl ,经常被用来实现递归。