On Wed, May 18, 2011 at 1:10 AM, rusi <rustompm...@gmail.com> wrote: >> Um, it is. Consider the simple function (lambda x, y: x + y). >> Mathematically, this function is recursive. Algorithmically, it is >> not. Do you disagree? > > See the definition of primitive recursion eg. > > http://en.wikipedia.org/wiki/Primitive_recursive_function#Definition > > (2 of the second set of "more complex" definitions) from where the > name 'primitive recursion' is presumably derived) > > And for the more general (wider) class of 'recursive' functions (in > the math sense aka computable functions) see a little below: > > http://en.wikipedia.org/wiki/Primitive_recursive_function#Relationship_to_recursive_functions
I know what primitive recursive and computable functions are, thanks. What you're failing to explain is why you would consider that function to be recursive from a programming standpoint. In programming, when we say a function is recursive, we mean that it is implemented using the technique of recursion, not that it is computable. Since we're throwing around Wikipedia links, see the definition in the first sentence at: http://en.wikipedia.org/wiki/Recursion_%28computer_science%29 In fact, the mathematical definition would not be useful for programming since to us a function is an implementation of an algorithm (I expect Lispers may quibble over this, but it is true even there). Thus, in programming, all functions are computable. > Of course I grant that the adjective 'recursive' is used differently > in computability and in programming but the roots are not all that > different. Not just the adjective 'recursive', but also the noun 'function'. I'm not sure of the exact etymology of 'recursive', although I would bet that the mathematical usage came first and the programming usage is a derivative of it. -- http://mail.python.org/mailman/listinfo/python-list
