Haskell 在函数中使用终止符

Question

我想了解更多关于函数终止的信息，例如：当 n 是自然数时终止在这个函数中是如何工作的或者我如何终止这个函数

sum :: Int -> Int
sum 0 = 0
sum n = n + sum (n - 1)

Answer 1

递归代码是这样工作的 - 有两个子句，一个根据自身定义自身，另一个通过返回单个值来终止计算。这里的终止子句是sum 0 = 0，sum的定义由sum n = n + sum (n-1).

给出

你可以用笔和纸算出来，参数n = 5:

n        sum   
5        5 + sum (4)
         5 + 4 + sum (3)
         5 + 4 + 3 + sum (2)
         5 + 4 + 3 + 2 + sum (1)
         5 + 4 + 3 + 2 + 1 + sum (0)
         5 + 4 + 3 + 2 + 1 + 0

因为我们指定sum(0)为0，所以计算到此结束。

计算可能会出错并且永远不会终止，原因有很多：

没有终止条款
永远不会达到终止条款

如果愿意，请考虑以下恶意代码：

badSum :: Int -> Int
badSum 6 = 6
badSum n = n + badSum (n-1)

badSum 5 -- locks up, press Ctrl-C

因为永远不会到达终止子句，所以递归永远不会终止。此外，对于您的 sum 和 n = -1.

的非法值

顺便说一句，Haskell 有两种基本的整数类型，Int 和 Integer。 Int 类型是一个长整数，而 Integer 是一个无限整数。 Int 更快，但 Integer 可能更适合递归，特别是在答案增长非常快的情况下 - 例如阶乘。您必须从一种类型转换（转换）为另一种类型，因为 Haskell 不会为您执行此操作。在这种情况下，toInteger 从 Int 转换为 Integer，更普遍的是 fromIntegral.

fact :: Int -> Int
fact 1 = 1
fact n = n * fact (n-1)

fact2 :: Int -> Integer
fact2 1 = 1
fact2 n = (toInteger n) * fact2 (n-1)

在这两种情况下，阶乘都是根据自身定义的，n = 1 的终止子句导致值为 1。两者都做了合理的工作，但对于更大的 n fact 开始表现确实很奇怪：

 n      fact                   fact2
 1                    1                              1
 5                  120                            120
10              3628800                        3628800
20  2432902008176640000            2432902008176640000
30   -8764578968847253504          265252859812191058636308480000000

因为 Int 是一个固定长度的整数，最终值会回绕，在这种情况下会产生负值。

最后，现实世界 Haskell 不会使用这样的递归。您的代码已临时替换了一个 sum 函数。从 1 到 n 的总和由 sum [1 .. n] 给出，阶乘由 product [1 .. n].

给出

Haskell 在函数中使用终止符

Haskell usnig termination in a function

haskell

function

termination