On May 18, 7:32 pm, Ian Kelly <ian.g.ke...@gmail.com> wrote: > 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#Relationshi... > > I know what primitive recursive and computable functions are, thanks.
Myself, my memory of things studied badly decades ago may be fuzzy :D ) Anyhow taking those links to be authoritative, what I am saying is: Coming from the computability side, there are 3 related but distinct definitions of recursive: 1. Anything computable is recursive -- general recursive or partial recursive (evidently there is some dispute re these definitions http://mathworld.wolfram.com/RecursiveFunction.html 2. Primitive recursive -- ie any function that is defined using - constant - successor - projection - composition - primitive recursion [This definition is recursive in a bad sense but let that be... The first use of the term is for the set of functions such that... The second is for a specific operation. Comes to the third use: 3. The *operation* of primitive recursion is exactly what programmers call recursion. In other words one specific and characteristic operation is used to give the name to the set being defined. > What you're failing to explain is why you would consider that function > to be recursive from a programming standpoint. As for putting + under the format of primitive recursion, it would go something like this (I guess) Matching up that definition Put h is what is being defined ie + (or plus) k = 1 f = id g(y, ic, x) = S(ic) #ignore y and x, ic is internal (recursive) call Gives plus(0, x) = x plus((S y), x) = S(plus(y, x)) -- http://mail.python.org/mailman/listinfo/python-list
