Haskell 如何计算斐波那契函数？

Question

我目前正在 Haskell 中查看此函数，其中 returns 位置 n

的斐波那契数列

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

现在，它编译，returns 正确的结果和一切......但我不明白 Haskell 如何计算这个函数。

难道 Haskell 不总是寻找一个合适的定义然后应用该定义直到它不再适用（例如达到基本情况）吗？

在那种情况下，这就是我想出的。例如，评估 fib 3

fib n = fib (n-1) + fib (n-2)
fib 3 = fib (3-1) + fib (3-2)
fib 3 = fib ((3-1)-1) + fib ((3-1)-2) + fib ((3-2)-1) + fib ((3-2)-2)
fib 3 = fib (((3-1)-1)-1) + fib (((3-1)-1)-2) +
        fib (((3-1)-2)-1) + fib (((3-1)-2)-2) + 
        fib (((3-2)-1)-1) + fib (((3-2)-1)-2) + 
        fib (((3-2)-2)-1) + fib (((3-2)-2)-2)
...

这可能会永远持续下去，而不会给出实际结果。但是，Haskellreturns一个结果。那我做错了什么？

Answer 1

定义中方程的顺序很重要。

部分

fib n = fib (n-1) + fib (n-2)

仅在前几行不适用时应用。也就是说，仅当 n 不是 0 或 1 时。因此，步骤

fib 3 = fib (3-1) + fib (3-2)
fib 3 = fib ((3-1)-1) + fib ((3-1)-2) + fib ((3-2)-1) + fib ((3-2)-2)

是错误的：fib (3-2) 是 fib 1 = 1，而不是 fib ((3-2)-1) + fib ((3-2)-2)。

另一种查看方式如下。整个 3 行定义可以使用 case 等价地表示为

fib n = case n of
        0 -> 0
        1 -> 1
        m -> fib (m-1) + fib (m-2)

Haskell 如何计算斐波那契函数？

How does Haskell evaluate the Fibonacci function?

haskell

recursion

fibonacci

reduction