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