这个斐波那契函数是如何工作的？

Question

谁能告诉我以下函数是如何工作的？

尤其是 fibu' 和元组？谢谢！

fibu :: Integer -> Integer
fibu x = fst (fibu' x)
      where fibu' 0 = (0, 0)
            fibu' 1 = (1, 0)
            fibu' n = (a + l, l)
                      where (l, a) = fibu' (n-1)

Answer 1

我们先来分析一下

fibu' 0 = (0, 0)
fibu' 1 = (1, 0)
fibu' n = (a + l, l)
    where (l, a) = fibu' (n-1)

这里我们有一个函数，它接受一个数字 i 和 returns 一个包含两个数字的二元组作为输入。两个数分别是 (F_i, F_i-1) 和 F _i 第 i 个斐波那契数。

前两个数字（i = 0 和 i = 1）是硬编码的（如 (0, 0) 和(1, 0))。但是我们当然不能对斐波那契值进行硬编码。如果 i 不是 0 或 1，最后一行将被触发。实施此案例是为了处理 i-1 案例。

在那种情况下我们递归计算fibu' (n-1)（所以包含(F_n-1, F_n的元组-2)，我们在前面两个斐波那契数列中计算出来，我们就知道（这就是斐波那契归纳关系F_n = F_n-1 + F_n-2). 所以这意味着我们可以 return (a+l, l)。因此，如果我们调用实例 fibu' 5，它将调用 fibu' 4、fibu' 3 等，直到我们到达 fibu' 1，然后我们将每次构造一个新的元组，它将继续计算最后两个斐波那契数，直到我们到达索引为 5.

的斐波那契数

现在 fibu' 的唯一问题是它 return 是一个二元组，用户通常希望得到一个简单的数字（i-th 斐波那契数）。所以现在我们定义一个函数：

fibu :: Integer -Integer
fibu x = fst (fibu' x)

这将 return 二元组的 第一个 项（即第 i 个斐波那契数） .

Answer 2

您可能已经看到了斐波那契数列的简单实现：

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

好吧，这个问题是该函数递归地调用自身两次。这些调用中的每一个都会再次调用自己两次......所以你最终会得到成倍增长的调用。

您所要求的实施方式确实解决了这个问题：returns 不仅是第 n 个斐波那契数，而且 n-th 和 n−1-th。然后 n+1 调用只需要一个额外的调用，而不是两个，因为那个调用给了它计算下一个元素所需的一切顺序。

对于最终结果，您不需要两个数字，但只需要一个，因此使用 fst.

丢弃倒数第二个值

这个斐波那契函数是如何工作的？

How does this Fibonacci function work?

recursion

haskell

fibonacci