Recursion

Consider one approach to defining or generating the set of natural numbers (Russell, 1920).  The set begins with 0.  The next number is 1, which can be defined as the successor of 0 – as s(0).  The next number is 2, which is the successor of 1 (s(1)), but is also the successor of the successor of 0 (s(s(0))).  In other words, the successor function can be used to create the entire set of natural numbers: {0, s(0), s(s(0)), s(s(s(0))), … }.

The definition of the natural numbers using the successor function is an example of simple recursion.  In general, a function is recursive in this sense when it operates by referring to itself.  The expression s(s(0)) is recursive because to determine its value the first successor function must determine the value of the second successor function that is placed within the first function’s parentheses.  That is, it is recursive because the successor function uses another version of itself.  Note that this is the simplest notion of recursion.  In the early 20^th century mathematicians began to use the term “recursion” to mean “computable”, which is a much more complicated concept.

Recursion is one method by which a finite system (like the Dedekind-Peano axioms) can produce infinite variety (like the set of natural numbers) (Russell, 1920).  In other words, cognitive scientists use recursion to show how the creativity of language can be generated by finite devices, and use this approach to support the claim that cognition is information processing – and to argue against Cartesian dualism.

References:

1. Russell, B. (1920/1993). Introduction To Mathematical Philosophy. New York: Dover Publications.

(Added September 2010)