为什么这会产生 StackOverflow 错误？

Question

最近开始使用Haskell，定义了这个看似简单的函数：

f 0 = 1
f x = x * f x - 1

然而，结果是：

GHCi, version 8.2.1: http://www.haskell.org/ghc/  :? for help
Prelude> f 0 = 1
Prelude> f x = x * f x - 1
Prelude> f 10
*** Exception: stack overflow
Prelude>

Answer 1

您的阶乘看似无辜，但事实并非如此。解析如下：

f 0 = 1
f x = x * (f x) - 1

如果我们使用 f 1 会怎样？

f 1 = 1 * (f 1) - 1 = 1 * (1 * (f 1) - 1) - 1
    = 1 * (1 * (1 * (f 1) - 1) - 1) - 1
    = 1 * (1 * (1 * (1 * (f 1) - 1) - 1) - 1) - 1
    = ...

我要到此为止了。这永远不会结束。它会建立一堆括号，有时整个塔会倒塌，最终导致堆栈溢出。

你必须使用括号：

f 0 = 1
f x = x * f (x - 1)

现在我们得到正确的结果：

f 1 = 1 * f (1 - 1) = 1 * f 0 = 1 * 1 = 1

请记住，这仅适用于实现文件。在 GHCi 中，您必须使用多行模式或分号：

ghci> f 0 = 1; f x = x * f (x - 1)
ghci> -- or
ghci> :{
ghci| f 0 = 0
ghci| f x = x * f (x - 1)
ghci| :}

否则后面的定义会影响前面的定义。请注意，您的提示可能有所不同。

为什么这会产生 StackOverflow 错误？

Why does this create a StackOverflow Error?

haskell

ghci