导航页

递归即为会调用自身的函数。递归计算是不定（indefinite）或增量的（incremental）。

递归在人类语言中很常见，但 Lambda 演算法中没有原生的递归概念，因为表达式是匿名的。但我们可以使用 Y 不动点组合子（Y fixed-point combinator）来实现不具名的递归。

阶乘!

阶乘（factorial）是经典的递归函数，你可能看见过类似 \(4!\) 的表达式，其中的 \(!\) 即为阶乘符号。

求值 \(4!\)：

4! = 4 * 3 * 2 * 1
        12 * 2 * 1
            24 * 1
                24

在 Haskell 中实现一个递归并不难：

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

比如，对于 factorial 4，这样求值：

factorial 4 =
  4 * factorial (4 - 1)
  4 * factorial 3
  4 * 3 * factorial (3 - 1)
  4 * 3 * factorial 2
  4 * 3 * 2 * factorial 1
  4 * 3 * 2 * 1 * factorial (1 - 1)
  4 * 3 * 2 * 1 * 0
  24

另一条路

上一篇文章中，我们介绍了 . 组合函数，它将第一个实参的结果，作为新实参传递给第二个实参。这与递归所需的类似，不过新实参需要传递给同一个函数，直到求值结束。

通常的函数组合是静态且确定的，而递归组合是不定的。函数应用的次数会根据参数变化，若没有终止点，应用可能是无限的。

像 Haskell 这样完全基于 Lambda 演算法的编程语言，用一个动词表达可以被求值的计算：应用（apply）。将一个函数应用于一个参数，并获得结果，是我们唯一能做的。无论 Haskell 提供了什么样的语法糖，使其看起来超越了这些功能。但本质上仍然是纯粹的 Lambda 演算法。

关于如何通过 Y 组合子在纯 Lambda 演算法中实现递归，可以看这篇较短的介绍或者更详细的这篇。

因此很容易编写一个根据参数应用特定次数的函数，类似 (.)：

applyTimes :: (Eq a, Num a) => a -> (b -> b) -> b -> b
applyTimes 0 f b =
  b
applyTimes n f b =
  f . applyTimes (n -1) f $ b

其中 n 为应用的次数，f 为接受的函数，b 为初始值。

applyTimes 5 (+1) 5
-- 10

Bottom

在 Haskell 中，\(\bot\) 或下界类型（bottom type）用于表示没有成功获得结果。

例如：

Prelude> let x = x in x
*** Exception: <<loop>>

当然也可以自己定义异常：

f :: Bool -> Int
f True  = error "blah"
f False = 0

Prelude> f False
0
Prelude> f True
*** Exception: blah

当然，偏函数会导致错误，所以也会有 \bot。

Prelude> :{
         f :: Bool -> Int
         f False = 0
         :}
Prelude> f False
0
Prelude> f True
*** Exception: <interactive>:24:1-11: 
  Non-exhaustive patterns in function f

全函数（total function）是偏函数（partial function）的反义词。权函数涵盖了所有可能输入的对应输出，否则就是偏函数。

先前的例子实质上类似：

f::Bool->Int
f False = 0
f _ = error $ "*** Exception: "
            ++ "Non-exhaustive "
            ++ "patterns in function f"

那如何将偏函数化为全函数呢？其中一种方式，是使用数据类型 Maybe：

data Maybe a = Nothing | Just a

Maybe 可以替代大多数需要 nil 或 null 的场景。它有两个构造器，Nothing 表示错误，因此不需要参数；Just 表示存在数据，因此需要一个参数用于保存数据。

f :: Bool -> Maybe Int 
f False = Just 0
f _ = Nothing

当然，请记得把 0 包一层 Just 否则会报错：

f :: Bool -> Maybe Int
f False = 0 :: Int
f _ = Nothing

Couldn't match expected type
      ‘Maybe Int’ with actual type ‘Int’
    In the expression: 0 :: Int
    In an equation for ‘f’: f False = 0 :: Int

菲波纳契数列

斐波纳契是一个从 1 开始，且每个数都是先前所有数的总和的数列。如：

1, 1, 2, 3, 5, 9, 13, 21, 34 ...

要实现它不难。

1. 我们应当考虑类型。由于菲波纳契数列是无限的，可能 Integral a => a -> a 会比 Integer -> Integer 好。
2. 考虑特殊值：

fibonacci :: Integral a => a -> a
fibonacci 0 = 0
fibonacci 1 = 1

3. 随后，我们很容易得出：

fibonacci :: Integral a => a -> a
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci x = (x - 1) + (x - 2)

以上即为关于递归的内容。