请看下面的（Haskell）代码：
fib=0:1:zipWith (+) fib (tail fib)
一位同事试图Assert这不是一个递归函数，因为fib只是一个用自身定义自身的列表，这与一个做同样事情的函数有些不同，我认为他在吸食可卡因。你觉得呢？
fib
kzmpq1sx1#
用zipWith定义的fibonacci不是递归函数，实际上没有函数参与，fib是一个列表（数据），它是懒惰地自定义的，利用了Haskell的懒惰语义，在某种意义上，你可以称它为递归列表或递归数据;而不是递归函数。要理解递归列表可能很困难，因为很少有编程语言能做到这一点，但你会注意到，在Haskell中，所有函数都只带一个参数。fib不带任何参数，因为它不是一个函数。由于没有涉及到函数，所以不可能有递归函数。你的同事不是在吸食可卡因，他是开明的（或者吸食可卡因，如果这是你对开明的定义的话）。
ep6jt1vc2#
天哪，真是个微妙的术语区分的老鼠窝。“这”是什么？
它不是递归函数，也不是递归数据，而是递归定义。正在定义什么？
根据这个定义，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"是递归数据结构，即使它不是递归定义的，并且实际上它可以由诸如++的递归函数来作用。短语“递归函数”的意思是“递归定义的函数”。短语“递归值”的意思是“递归定义的值”，例如存在于非严格语言中的：严格语言具有“值递归”问题。如果您认为这是迂腐的，请尝试在 total 编程语言中以这种方式定义fib，您将发现“递归定义”的概念分裂为“通过结构递归定义”（以停止的方式消耗数据）和“通过保护的核心递归定义”（以一种可以运行的方式产生数据），而fib属于后一种类型。在这种情况下，fib的生产率关键取决于zipWith的懒惰。当然，在 haskell 的情况下，你不需要担心任何东西来弄清楚什么是定义，只需要弄清楚它是否有一半的机会真正起作用。
\ f xs ys -> xs
zipWith
"fred"
++
lpwwtiir3#
它是递归的，你能分辨出来是因为=的左行名字也出现在右行。但是，它 * 不是 * 函数，因为fib的类型不包含->，所以可以分辨出来。
=
->
km0tfn4u4#
由于大多数答案都支持您的同事的 * 职能 * 部分：“fib * 不是 * 递归函数。”我想详细说明Conor McBride在他的回答中暗示的递归部分。对于fib给出的定义是 * 非 * 递归的，它是 * 共递归的 *。协同递归看起来很像递归，正如许多海报所指出的，定义的LHS也出现在RHS上。但是没有基础情况。递归和协同递归“运行在相反的方向”。上面的fib的定义从初始值0和1开始，并从那里“向上”移动并继续下去。另一方面，递归定义，比如说（计算）第n个斐波那契数的函数
fib' 0 = 0 fib' 1 = 1 fib' n = fib' (n-1) + fib' (n-2)
从第n个数字“向下”行走，直到它到达基本情况并在那里停止。我想这在两点上都证明了瘾君子的正确：-）要进一步阅读，请查看Corecursion上的wikipedia文章和链接。如果你能拿到这本书，Kees Doets和Jan货车Eijck所著的 The Haskell Road to Logic，Maths and Programming 第10章可能值得一看。
nnsrf1az5#
你给出的例子是递归的，但斐波那契数列本质上并不一定是递归的，它有iterative versions of the algorithm，甚至explicit functions。
wwodge7n6#
他在破解--上面的函数显然是递归的。
mgdq6dx17#
除了这里的Haskell实现，斐波那契数是一个由递归关系定义的序列。从数学上讲，每一项都被定义为前面各项的 * 函数 *。用数学语义击败他。
5w9g7ksd8#
要使这个函数成为递归函数，它必须既是递归函数又是函数，正如sepp2k指出的，它显然是递归的，因为名称fib出现在=的两边，也就是说，fib是根据它自己定义的。它是一个函数吗？不是根据它的类型。在haskell中，我们称一个0参数函数为“data”。所以fib的这个定义创建了一个递归数据结构，但不是递归函数。
8tntrjer9#
虽然很多人在评论中都在争论定义是否是函数，但大家似乎都同意它是递归的。至于函数/非函数参数，在Haskell中，从程序员的Angular 来看，它无关紧要！因为函数和数据结构都是惰性求值的，所以一个值和一个没有参数返回值的函数是无法区分的。你得到的是一个整数列表，惰性地和递归地求值。fib同时也是一个“整数列表”，“返回整数列表的无参数函数”、“返回整数的无参数函数列表”、以及“返回整数的无参数函数列表的无参数函数”。老实说，这并不重要。语言并不区分这四种类型。类型理论也不区分这四种类型（还有无数其他类型：一个没有参数的函数返回任何一个都是有效的，就像一个没有参数的函数返回那个一样，无穷大）。但它是递归的。
9条答案
按热度按时间kzmpq1sx1#
用zipWith定义的fibonacci不是递归函数，实际上没有函数参与，fib是一个列表（数据），它是懒惰地自定义的，利用了Haskell的懒惰语义，在某种意义上，你可以称它为递归列表或递归数据;而不是递归函数。
要理解递归列表可能很困难，因为很少有编程语言能做到这一点，但你会注意到，在Haskell中，所有函数都只带一个参数。
fib不带任何参数，因为它不是一个函数。由于没有涉及到函数，所以不可能有递归函数。你的同事不是在吸食可卡因，他是开明的（或者吸食可卡因，如果这是你对开明的定义的话）。
ep6jt1vc2#
天哪，真是个微妙的术语区分的老鼠窝。“这”是什么？
它不是递归函数，也不是递归数据，而是递归定义。
正在定义什么？
根据这个定义，
fib是什么类型的东西？整数列表（或者任何旧的数字内容列表）。
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"是递归数据结构，即使它不是递归定义的，并且实际上它可以由诸如++的递归函数来作用。短语“递归函数”的意思是“递归定义的函数”。短语“递归值”的意思是“递归定义的值”，例如存在于非严格语言中的：严格语言具有“值递归”问题。
如果您认为这是迂腐的，请尝试在 total 编程语言中以这种方式定义
fib，您将发现“递归定义”的概念分裂为“通过结构递归定义”（以停止的方式消耗数据）和“通过保护的核心递归定义”（以一种可以运行的方式产生数据），而fib属于后一种类型。在这种情况下，fib的生产率关键取决于zipWith的懒惰。当然，在 haskell 的情况下，你不需要担心任何东西来弄清楚什么是定义，只需要弄清楚它是否有一半的机会真正起作用。lpwwtiir3#
它是递归的，你能分辨出来是因为
=的左行名字也出现在右行。但是，它 * 不是 * 函数，因为
fib的类型不包含->，所以可以分辨出来。km0tfn4u4#
由于大多数答案都支持您的同事的 * 职能 * 部分：“
fib* 不是 * 递归函数。”我想详细说明Conor McBride在他的回答中暗示的递归部分。对于
fib给出的定义是 * 非 * 递归的，它是 * 共递归的 *。协同递归看起来很像递归，正如许多海报所指出的，定义的LHS也出现在RHS上。但是没有基础情况。递归和协同递归“运行在相反的方向”。
上面的
fib的定义从初始值0和1开始，并从那里“向上”移动并继续下去。另一方面，递归定义，比如说（计算）第n个斐波那契数的函数从第n个数字“向下”行走，直到它到达基本情况并在那里停止。
我想这在两点上都证明了瘾君子的正确：-）
要进一步阅读，请查看Corecursion上的wikipedia文章和链接。如果你能拿到这本书，Kees Doets和Jan货车Eijck所著的 The Haskell Road to Logic，Maths and Programming 第10章可能值得一看。
nnsrf1az5#
你给出的例子是递归的，但斐波那契数列本质上并不一定是递归的，它有iterative versions of the algorithm，甚至explicit functions。
wwodge7n6#
他在破解--上面的函数显然是递归的。
mgdq6dx17#
除了这里的Haskell实现，斐波那契数是一个由递归关系定义的序列。从数学上讲，每一项都被定义为前面各项的 * 函数 *。用数学语义击败他。
5w9g7ksd8#
要使这个函数成为递归函数，它必须既是递归函数又是函数，正如sepp2k指出的，它显然是递归的，因为名称
fib出现在=的两边，也就是说，fib是根据它自己定义的。它是一个函数吗？不是根据它的类型。在haskell中，我们称一个0参数函数为“data”。所以
fib的这个定义创建了一个递归数据结构，但不是递归函数。8tntrjer9#
虽然很多人在评论中都在争论定义是否是函数，但大家似乎都同意它是递归的。
至于函数/非函数参数，在Haskell中，从程序员的Angular 来看，它无关紧要！因为函数和数据结构都是惰性求值的，所以一个值和一个没有参数返回值的函数是无法区分的。你得到的是一个整数列表，惰性地和递归地求值。
fib同时也是一个“整数列表”，“返回整数列表的无参数函数”、“返回整数的无参数函数列表”、以及“返回整数的无参数函数列表的无参数函数”。老实说，这并不重要。语言并不区分这四种类型。类型理论也不区分这四种类型（还有无数其他类型：一个没有参数的函数返回任何一个都是有效的，就像一个没有参数的函数返回那个一样，无穷大）。
但它是递归的。