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

Question

考虑以下(Haskell)代码：

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

一位同事试图断言这不是一个递归函数，因为fib只是一个用自己定义自己的列表，并且在某种程度上与执行相同操作的函数不同。我想他在吸可口可乐。

你认为如何？

Answer 1

使用zipWith的斐波纳契定义不是一个递归函数，实际上没有涉及到任何函数，fib是一个懒惰自定义的列表(数据)，利用了Haskell的懒惰语义。在某种意义上，你可以称它为递归列表或递归数据；但不能称其为递归函数。

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

你的同事不是在吸可口可乐，他是开明的(或者吸食可口可乐，如果这是你对开悟的定义)。

Answer 2

天哪，多么微妙的术语区别的老鼠窝。什么是“这”？

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

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

什么是被定义的？

fib

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

[Integer]

一个整数列表(或者可能是任何旧数字的列表)。

fib是一个函数吗？不，这是一个列表。fib是递归定义的吗？是。如果我们用相同类型的非递归函数(例如\ f xs ys -> xs)替换zipWith，fib会被递归定义吗？是的，尽管它可能是一个不同的递归定义的列表。

fib是循环列表吗？不是的。“递归数据结构”是否意味着“循环数据结构”？不是根据Hoare的论文“递归数据结构”：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"是一种递归数据结构，即使它不是递归定义的，而且确实可以由递归函数(如++ )操作。

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

如果您认为这很学究，请尝试在整个编程语言中以这种方式定义fib，您会发现“递归定义”的概念分为“通过结构递归定义”(以一种停止的方式消费数据)和“通过守卫的共递归定义”(以一种过去的方式产生数据)，而fib属于后一种。在这种情况下，fib的生产力在很大程度上取决于zipWith的懒惰。当然，在Haskell的设置中，你不需要担心任何东西来弄清楚什么是某种定义，只需要弄清楚它是否有一半的机会实际工作。

Answer 3

它是递归的。你可以看出来，因为=的LHS上的名字也会出现在RHS上。

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