Menu
Consider the following (Haskell) code:
fib=0:1:zipWith (+) fib (tail fib)
A coworker is trying to assert that this 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?
754
In mathematics, things are often defined recursively. For example, the Fibonacci numbers are often defined recursively. The Fibonacci numbers are defined as the sequence beginning with two 1's, and where each succeeding number in the sequence is the sum of the two preceeding numbers.
Fibonacci series cannot be easily represented using an explicit formula. We therefore describe the Fibonacci series using a recursive formula, given as, F0 = 0, F1= 1, Fn = Fn-1 + Fn-2, where n > 1.
The logic of calculating nth Fibonacci number is implemented in this method and it does that without using recursion. It uses a simple for loop to iterate until the nth number and calculate Fibonacci number using the following formula : f(n) = f(n-1) + f(n-2);
We define a function MathML by MathML, where MathML. Then MathML for any MathML. This proves that f is a Fibonacci function. Note that if a Fibonacci function is differentiable on R, then its derivative is also a Fibonacci function.
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).
95
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.
34
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
