考虑以下(Haskell)代码:
fib=0:1:zipWith (+) fib (tail fib)
同事试图断言这不是一个递归函数,因为fib它只是一个用自身定义自己的列表,并且与执行相同操作的函数有某种不同.我认为他吸烟了.
你怎么看？
Lie*_*yan 14
使用zipWith的fibonacci定义不是递归函数,事实上没有涉及函数,fib是一个利用Haskell的懒惰语义懒惰自定义的列表(数据).从某种意义上说,你可以称之为递归列表或递归数据; 但不是递归函数.
因为很少有编程语言有任何接近,所以很难将你的头包裹在递归列表中,但是你会注意到在Haskell中所有函数只需要一个参数.fib不带任何参数,因为它不是一个函数.由于不涉及任何功能,因此不能具有递归功能.
你的同事不吸烟,他是开明的(或吸烟裂缝,如果这是你对启蒙的定义).
pig*_*ker 11
我的,这是一个微妙的术语区别的老鼠窝.这是什么"？
fib=0:1:zipWith (+) fib (tail fib)
它不是递归函数.它不是递归数据.这是一个递归定义.
什么是定义？
fib
fib根据这个定义,什么类型的东西？
[Integer]
整数列表(或者可能是任何旧数字内容的列表).
是fib功能吗？不,这是一个清单.是fib递归定义？是.将fib被递归定义,如果我们换成zipWith由同一类型(例如非递归函数\ f xs ys -> xs)？是的,虽然它将是一个不同的递归定义列表.
是fib循环列表吗？不是."递归数据结构"是指"循环数据结构"吗？不是根据Hoare的论文"递归数据结构":http://portal.acm.org/book_gateway.cfm？ id = 63445&type = pdf&bookpath =%F2700000%2F63445%2Fcb-p217-hoare.pdf&coll=&dl=&CFID=15151515& CFTOKEN = 6184618
在类型设置中,"递归数据结构"意味着不多于或少于"递归定义类型的居民".相应地"fred"是递归数据结构,即使它不是递归定义的,并且实际上它可以通过诸如的递归函数来作用++.
短语"递归函数"表示"递归定义的函数".短语"递归值"意味着"递归定义的值",例如存在于非严格语言中:严格的语言具有"值递归"问题.
如果你认为这是迂腐的,尝试fib用完整的编程语言定义那种方式,你会发现"递归定义"的概念分裂为"通过结构递归定义"(以停止的方式消耗数据)和"定义"通过保护的corecursion"(以一种方式产生数据),这fib是后一种.在这种情况下,生产力的fib关键取决于懒惰zipWith.当然,在Haskell设置中,你不需要担心任何这些东西来弄清楚什么是某种定义,只是想知道它是否有一半的实际工作机会.