这个斐波那契数列函数是递归的吗？

Question

考虑以下 (Haskell) 代码：

fib=0:1:zipWith (+) fib (tail fib)

一位同事试图断言这不是一个递归函数，因为 fib 只是一个用自身定义自身的列表，并且与执行以下操作的函数有所不同：相同的。我认为他在吸可卡因。

你怎么认为？

Answer 1

zipWith 的 fibonacci 定义不是一个递归函数，实际上没有涉及任何函数，fib 是一个延迟自定义的列表（数据），利用了 Haskell 的延迟语义。从某种意义上说，你可以称之为递归列表或递归数据；但不是递归函数。

你可能很难理解递归列表，因为很少有编程语言有任何接近的东西，但你会注意到，在 Haskell 中，所有函数都只需要一个参数。 fib 不接受任何参数，因为它不是一个函数。由于不涉及函数，所以不能有递归函数。

你的同事没有吸可卡因，他是开明的（或者吸可卡因，如果这是你对开明的定义）。

Answer 2

天哪，术语之间的微妙区别简直就是老鼠窝。 “这个”是什么？

fib=0:1:zipWith (+) fib (tail fib)

它不是递归函数。它不是递归数据。这是一个递归定义。

正在定义什么？

fib

根据这个定义，fib 是什么类型的东西？

[Integer]

整数列表（或者可能是任何旧数字内容的列表）。

fib 是一个函数吗？不，这是一个列表。 fib 是递归定义的吗？是的。如果我们将 zipWith 替换为相同类型的非递归函数（例如 \ f xs ys -> xs），fib 是否会被递归定义？是的，尽管这将是一个不同的递归定义列表。

fib 是循环列表吗？不是。“递归数据结构”是指“循环数据结构”吗？不是根据霍尔的论文“递归数据结构”：http://portal.acm.org/book_gateway.cfm?id=63445&type=pdf&bookpath= %2F70000%2F63445%2Fcb-p217-hoare.pdf&coll=&dl=&CFID=15151515&CFTOKEN=6184618

在类型化设置中，“递归数据结构”的含义不大于或小于“居民”递归定义的类型”。相应地，“fred”是一种递归数据结构，尽管它不是递归定义的，但实际上它可以被诸如++之类的递归函数所操作。

短语“递归函数”的意思是“递归定义的函数”。短语“递归值”的意思是“递归定义的值”，例如存在于非严格语言中：严格语言存在“值递归”问题。

如果您认为这很迂腐，请尝试在total编程语言中以这种方式定义fib，您会发现“递归定义”的概念分解为“定义结构递归”（以停止的方式消耗数据）和“通过受保护的核心递归定义”（以持续的方式生成数据），而 fib 属于后者。在这种情况下，fib 的生产力很大程度上取决于 zipWith 的惰性。当然，在 Haskell 设置中，您不需要担心任何这些东西来弄清楚某个东西是什么类型的定义，只需弄清楚它是否有一半的机会实际工作。

Answer 3

这是递归的。您可以看出，因为 = 左侧的名称也出现在右侧。

然而，它不是一个函数。您可以看出，因为 fib 的类型不包含 ->。

Answer 4

由于大多数答案都支持您的同事关于以下函数部分：“fib 是不是递归函数。”我想详细说明康纳·麦克布莱德在他的回答中暗示的递归部分。

fib 的定义是非递归，而是协同递归。

联合递归看起来很像递归，因为正如许多海报所指出的那样，定义的左侧也出现在右侧。但没有基本情况。递归和核心递归“方向相反”。

上面的 fib 定义从初始值 0 和 1 开始，并从那里“向上”移动并继续下去。
另一方面，例如（计算）第 n 个斐波那契数的递归定义

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

从第 n 个数“向下”移动，直到到达基本情况并停止。

我想这证明了这两点上的破解者:-)

---

要进一步阅读，请查看维基百科关于 Corecursion 以及那里的链接。如果您能上手，Kees Doets 和 Jan van Eijck 所著的The Haskell Road to Logic, Maths andProgramming的第 10 章可能值得一看。

Answer 5

您给出的示例是递归的。但斐波那契数列本质上不一定是这样。有算法的迭代版本，甚至显式函数。

Answer 6

他已经破解了——上面的函数显然是递归的。

Answer 7

除了此处的 Haskell 实现之外，斐波那契数是由递归关系定义的序列。从数学上来说，每一项都被定义为前面各项的函数。用数学语义打败他。

Answer 8

要使其成为递归函数，它必须既是递归函数又是函数。正如 sepp2k 指出的那样，它显然是递归的，因为名称 fib 出现在 = 的两侧。也就是说，fib 是根据其自身定义的。

它是一个函数吗？不根据其类型。在 haskell 中，我们将 0 参数函数称为“data”。因此，fib 的定义创建了一个递归数据结构，但不是一个递归函数。

Answer 9

我认为有一个相当大的理由不认为这个定义是递归函数（许多其他答案似乎缺失了？！），这与这个定义如何实现 O(n) 性能直接相关。

您可以定义一个几乎相同的递归函数（只是忽略参数）来计算斐波那契数，如下所示：

fib :: () -> [Integer]
fib _ = 0 : 1 : zipWith (+) (fib ()) (tail $ fib ())

这甚至可能是您考虑将 fib 的定义翻译成无需打结的语言的方式。

但是，如果您实际尝试一下，您会发现比非功能版本慢得多。

这是因为 Haskell 的按需调用语义。当 fib 只是一个根据自身定义的整数列表时，fib 直接指向一个整数列表，其末尾是一个未计算的 thunk。递归实际上是指向同一个列表的开头。这意味着在计算新术语时，根据需要进一步评估此列表的任何工作本质上都会被重用。

相反，函数版本实际上会 CALL 自身，并在每次递归调用时重做所有工作。 Haskell 不会进行任何类型的自动记忆，因此这将具有与 fib 的简单定义相关的可怕的 O(2^n) 时间复杂度。

Answer 10

虽然评论中很多人都在争论这个定义是否是函数，但大家似乎都同意它是递归的。

至于函数/非函数参数，在 Haskell 中，从程序员的角度来看，它并不重要！因为函数和数据结构都是惰性计算的，所以值和无参数返回值的函数是无法区分的。您拥有的是一个整数列表，以惰性和递归方式求值。 fib 同时是一个“整数列表”、一个“返回整数列表的无参数函数”、“返回整数的无参数函数列表”和“返回整数的无参数函数”无参数返回整数的函数列表”。

老实说这并不重要。语言对这四种之间没有区别。类型理论对这四种类型没有区别（以及无数其他类型：没有参数的函数返回其中任何一个都同样有效，就像没有参数的函数返回该函数一样，无穷无尽）。老实说，无论您是否将 fib 称为“函数”，都没有什么区别。

但它是递归的。