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不是0,递归
- 我们将得到的1和本来的2相乘,得到2,即(2 × 1 × 1),返回它
- 2不是0,所以“递归”
- 我们将得到的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)
,然后就会没完没了。无限循环不是我们想要的。一般来说:特殊情况应该置于前,一般情况置于后。
练习 |
---|
|
一次小小的跑题
编辑此段落欲为习惯命令式语言如c或Java的用户提供指导。
在命令式语言中,“循环”是很普遍的。在命令式语言中,阶乘函数的通常写法是用一个“for”循环,如下(用c语言):
例子: 命令式语言中的阶乘函数
int factorial(int n) { int res = 1; for (i = 1; i <= n; i++) res *= i; return res; }
这在Haskell中直接实现是不可能的,因为改变变量res
和i
的值(以一种破坏性的方式)是不可以的。然而,我们依然可以将一个循环转换为同作用的递归形式。重点是让每个需要改变的循环变量变成一个递归函数的参数。比如,以下将上个循环“直译”为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
的例子一样)。当然,更小的参数也可以由其他方式产生。
练习 |
---|
|
基于表的递归
编辑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
订在前面。
这就是模式:在基于表的函数中,基线通常和空表相关,递归区通常会把表的尾部再传回函数自身以递归,这样表会越来越小。
练习 |
---|
给出以下基于表的函数的递归定义。对每一题,想想基线是什么,而递归区又如何,又如何做到参数越来越小?
|
递归几乎是所有表函数和数字函数的实现方法。下一次你再遇到基于表的函数时,先看看空表时的情况,再看看不空时的情况,也就知道这个算法是不是递归的了。呵呵。
不要太爱递归
编辑虽然我们对递归有个牢固的理解很重要,但这并不意味着在Haskell中我们要时时用递归编东西。事实上,有各种各样的用递归函数标准库,你只需要使用它们就可以了。比如,一种实现factorial(阶乘)函数的简单方式是这样的:
例子: 用标准库实现 factorial 函数
factorial n = product [1..n]
简直跟作弊差不多,对吧? :) 这就是有经验的 Haskell 程序员会如何写程序,他们不会动辄祭起递归这个法宝。当然, product
函数的本质就是表递归[4],但当我们用这种方式写代码的时候,不用操心其实现方式了。
概要
编辑递归是一种在函数定义内部调用自身的一种做法。它几乎都是由两种成分构成:基线和递归区。递归在处理表和数字时特别有用。
递归 |
习题解答 |
Elementary Haskell |
Haskell |
Haskell基础
>> 初级Haskell
>> Haskell进阶
>> Monads
|
注释
编辑- ↑ 在数学上,n的阶乘用n!表示,但Haskell可没有这种语法,所以这里我们不会这样用。
- ↑ 事实上,定义0的阶乘是1绝非任意,而是因为0的阶乘代表了 empty product.
- ↑ 这并非巧合,没有变量,递归是实现控制结构的唯一方法。这听起来很像限制,但只要习惯了,它绝不会碍手碍脚。
- ↑ 事实上,这个函数叫做
foldl
,经常被用来实现递归。