Home Original page

English Idiom in Unix: Directory Recursively

Ian Kelly ian.g.kelly at gmail.com
Wed May 18 10:32:29 EDT 2011 
On Wed, May 18, 2011 at 1:10 AM, rusi <rustompmody at 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.
More information about the Python-list mailing list