Is this Fibonacci sequence function recursive?

Consider the following (Haskell) code:

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

A coworker is trying to assert that thi开发者_运维问答s is not a recursive function because fib is simply a list that defines itself with itself and that is somehow different than a function that does the same. I think he's smoking crack.

What do you think?

The fibonacci definition with zipWith is not a recursive function, in fact there is no function involved, fib is a list (data) that is lazily self-defined, utilizing Haskell's lazy semantic. In a sense, you can call it recursive list or recursive data; but not recursive function.

It may be difficult to wrap your head around recursive list since very little programming languages have anything close, but you'll notice that in Haskell all functions takes exactly one paramater. fib does not take any parameter, because it's not a function. Since there is no function involved, you can't have recursive function.

Your coworker isn't smoking crack, he's enlightened (or smoking crack, if that's your definition of enlightenment).

My, what a rat's nest of subtle terminological distinctions. What is "this"?

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

It is not a recursive function. It is not recursive data. It is a recursive definition.

What is being defined?

fib

What type of thing is fib, according to this definition?

[Integer]

A list of integers (or perhaps a list of any old numeric stuff).

Is fib a function? No, it is a list. Is fib recursively defined? Yes. Would fib be recursively defined if we replaced zipWith by a nonrecursive function of the same type (e.g. \ f xs ys -> xs)? Yes, although it would be a different recursively defined list.

Is fib a cyclic list? No. Does "recursive data structure" mean "cyclic data structure"? Not according to Hoare's paper, "Recursive Data Structures": http://portal.acm.org/book_gateway.cfm?id=63445&type=pdf&bookpath=%2F70000%2F63445%2Fcb-p217-hoare.pdf&coll=&dl=&CFID=15151515&CFTOKEN=6184618

In a typed setting, "recursive data structure" means no more or less than "inhabitant of a recursively defined type". Correspondingly "fred" is a recursive data structure, even though it is not recursively defined, and indeed it can be acted upon by recursive functions such as ++.

The phrase "recursive function" means "recursively defined function". The phrase "recursive value" means "recursively defined value", such as exist in nonstrict languages: strict languages have the "value recursion" problem.

And if you think that's pedantic, try defining fib that way in a total programming language, and you'll discover that the notion of "recursive definition" splits into "definition by structural recursion" (consuming data in a way which stops) and "definition by guarded corecursion" (producing data in a way which goes), and that fib is of the latter variety. In that setting, the productivity of fib depends crucially on the laziness of zipWith. In the Haskell setting, of course, you don't need to worry about any of that stuff to figure out what sort of definition something is, just to figure out whether it has half a chance of actually working.

It's recursive. You can tell because the name on the LHS of the = also appears on the RHS.

It is however not a function. You can tell because the type of fib does not contain a ->.

Since most answers support your coworker with respect to the function part of: "fib is not a recursive function." I'd like to elaborate on on the recursive part Conor McBride hinted at in his answer.

The definition given for fib is not recursive, it is co-recursive.

Co-recursion looks a lot like recursion in that, as many posters have pointed out, the LHS of the definition appears on the RHS too. But there is no base case. Recursion and corecursion "run in opposite directions".

The above definition of fib starts from the initial values 0 and 1 and moves "up" from there and keeps on going. On the other hand a recursive definition of, say (a function calculating) the n-th Fibonacci number

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

walks "downwards" from the n-th number until it reaches the base cases and there stops.

I guess this vindicates the crackhead in both points :-)

For further reading check out the wikipedia article on Corecursion and the links there. If you can get you hands on it, Chapter 10 of The Haskell Road to Logic, Maths and Programming by Kees Doets and Jan van Eijck may be worth a peek.

The example you've given is recursive. But the Fibonacci sequence by nature doesn't have to be. There are iterative versions of the algorithm, and even explicit functions.

He's on crack - the above function is clearly recursive.

Aside from the Haskell implementation here, the Fibonacci Numbers are a sequence defined by a recurrence relation. Mathematically speaking, each term is defined as a function of the preceding terms. Defeat him with mathematical semantics.

For this to be recursive function, it needs to be both recursive and a function. As sepp2k points out, it's clearly recursive because the name fib appears on both sides of the =. That is, fib is defined in terms of itself.

Is it a function? Not according to its type. In haskell, we call a 0-argument function "data". So this definition of fib creates a recursive data structure, but not a recursive function.

Although many people in the comments are arguing whether or not the definition is a function, but everyone seems to agree that it is recursive.

As for the function/nonfunction argument, in Haskell, from the programmer's point of view, IT DOESN'T MATTER! Because both functions and data structures are evaluated lazily, a value and a function of no arguments returning a value are indistinguishable. What you have is a list of integers, evaluated lazily and recursively. fib is simultaneously a "list of integers", a "function of no arguments returning a list of integers", a "list of functions of no arguments returning integers", and "a function of no arguments returning a list of functions of no arguments returning integers".

It honestly does not matter. The language makes no distinction between the four. Type theory makes no distinction between the four (and countless others: a function of no arguments returning any of those is equally valid, as is a function of no arguments returning that, ad infinitum). It honestly makes no difference whether or not you call fib a "function" or not.

But it is recursive.