Haskell/解决方案/递归

阶乘函数

练习

将阶乘函数输入 Haskell 源文件，并将其加载到 GHCi 中。
尝试 factorial 5 和 factorial 1000 之类的示例。
- factorial (-1) 怎么样？为什么会这样？
一个数字 n 的双阶乘是 1（或 2）到 n 之间的隔一个数字的乘积。例如，8 的双阶乘是 8 × 6 × 4 × 2 = 384，而 7 的双阶乘是 7 × 5 × 3 × 1 = 105。在 Haskell 中定义 doubleFactorial 函数。

factorial 可以定义如下

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

输入 factorial (-1) 应该会显示消息 *** Exception: stack overflow。这是因为根据定义，factorial (-1) 是 (-1) * factorial (-2)，即 (-1) * (-2) * factorial (-3)。这将永远不会停止，因此函数将一直运行，直到它耗尽内存。
doubleFactorial 可以定义如下

doubleFactorial 0 = 1
doubleFactorial 1 = 1
doubleFactorial n = n * doubleFactorial (n-2)

其他递归函数

练习

类似于我们上面对 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。（小提示：阅读紧接这些练习的段落的最后一句话。）

1. 5 × 4

4 不等于 1，因此我们递归：计算 5 × 3

3 不等于 1，因此我们递归

2 不等于 1，因此我们递归

1 等于 1，因此我们返回 5

我们将当前数字 5 加到递归结果 5 中。我们得到 10

我们将当前数字 5 加到递归结果 10 中。我们得到 15

我们将当前数字 5 加到递归结果 15 中。我们得到 20。

2.

power x 0 = 1
power x y = x * power x (y-1)

3.

addition x 0 = x
addition x y = plusOne (addition x (y-1))

4.

log2 1 = 0
log2 n = 1 + log2 (n `div` 2) -- the "`" make div into infix notation

基于列表的递归

练习

为以下基于列表的函数给出递归定义。在每种情况下，考虑基本情况是什么，然后考虑一般情况在比它小的所有事物方面会是什么样子。

replicate :: Int -> a -> [a]，它接受一个元素和一个计数，并返回一个列表，其中该元素重复了该次数。例如，replicat 3 'a' = "aaa"。（提示：考虑任何计数为 0 的内容的副本应该是多少；计数为 0 是你的“基本情况”。）
(!!) :: [a] -> Int -> a，它返回给定“索引”处的元素。第一个元素位于索引 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')]。
使用辅助函数和累积参数定义 length，如 factorial 的循环式替代版本。

1-3 的答案，在一个代码块中

replicat 0 _     = []
replicat n thing = thing : replicat (n-1) thing

[]     !! _ = error "Index too large" -- An empty list has no elements.
(x:_)  !! 0 = x
(x:xs) !! n = xs !! (n-1)

zip []     _      = []
zip _      []     = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

(x:xs) 不匹配空列表，因此你也可以有

zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip _      _      = []

以下是累积的 length

length xs = go 0 xs
    where
    go acc []     = acc
    go acc (_:xs) = go (acc + 1) xs