Subject: Recursion
From: "William J. Rapaport"
Date: Sat, 13 Feb 2010 12:00:01 -0500 (EST)
A student writes:
"The whole recursive function definition is a bit difficult for me to
grasp. Would it be correct to say that recursive functions are
functions that can be reduced to, or are themselves functions that
produce, ordered pairs through formulations of Peano's axioms?"
Reply:
Not quite. First, functions (recursive or otherwise) don't *produce*
ordered pairs; they are *correlations* of pairs of things--only
algorithms "produce" an output from an input.
Second, although we've been looking only at functions defined on the
natural numbers--which, in turn, are characterized axiomatically by
Peano's axioms--that's just one example; recursion is a much more
general notion.
(For more on Peano's axioms, see:
http://mathworld.wolfram.com/PeanosAxioms.html
http://en.wikipedia.org/wiki/Peano_axioms )
In fact, technically speaking, I haven't yet defined recursive
*functions*; we'll get to that on Monday (I hope). What I've been doing
so far is giving recursive *definitions* of various concepts. Recursive
*functions* and recursive *definitions* are related, but different.
A recursive (or "inductive") *definition* proceeds by first giving some
"free samples" of the concept being defined (these are the "basic
building blocks" of the concept, the simplest or "atomic" or
"primitive" examples of it) and then giving some rules that tell you
how to construct new examples (which are more "complex" or
"molecular"--to continue my chemical metaphor) of the concept from ones
that you already have.
For some examples of recursive definitions, see Sect. 7 of the summary
for my CSE 191, Discrete (Mathematical) Structures, course:
http://www.cse.buffalo.edu/~rapaport/191/F09/summary.html
For more links about recursion in general
(including both recursive definitions and recursive functions),
see my webpage "Recursion & Induction":
http://www.cse.buffalo.edu/~rapaport/191/F09/recursion.html