[PREV - PRETTY_TRUE]    [TOP]

RECURSIVE_DEFINITION

                                                   June 14, 2004

A concept familiar to
most computer geeks is "recursion":

Sometimes you have a routine
which calls itself, i.e. which
is defined in terms of itself.

That seems tremendously paradoxical
when you first encounter the idea,
but a few examples make it clear how
it works.

The trick is that the routine
can not *always* call itself
(which would result in an
infinite loop), instead there's         In practice this "infinite loop"
a conditional in there; the             would be a stack blow-up:
algorithm checks something to
see if it should call itself again.                      Every call pushes
                                                         information on
                                                         the stack.
                                 See the book            Eventually you
When philosophers run            "Goedel, Escher,        run out of room
into similar tangles,            Bach" by Hofstader      to store it.
they tend to throw up            for endless
their hands and say              tedious examples          Recursion isn't
"circular reasoning"!            of recursion in           used very often
                                 different contexts.       because it tends
                 CIRCLES                                   to run into the
   It's at least                                           memory limits
   possible that                  (It may be Hofstader     of the computer
   that's a                       says something much      (and the mental
   premature                      like I'm saying here.    limits of the
   reaction.                      I fell asleep            programmer).
                                  half-way through that
   Having something               book, so I wouldn't         Though some
   defined in terms               know.)                      languages (or
   of itself is not                                           more to the
   by itself a sign                                           point, the
   of nonsense.                                               cultures that
                                     A typical                go with the
      However: the odds              programmer's             languages) are
      seem good that some            first example            more suited to
      sort of ethical                is computation           recursion than
      philosophy with a              of factorials,           others:
      recursively looping            that is,
      structure to it                                         The children
      would not be very              5! = 5*4*3*2*1           of lisp.
      satisfying.
                                     which can be
                                     thought of as
      I would fear that the
      loops would be                 5! = 5*4!
      treated as a mystical
      knot which could be            The factorial for
      used to generate               N is defined in
      rationalizations for           terms of factorial
      any course of action.          for (N-1).

                                     You know you're done
                                     when N-1 is 0;
                                     0!=1 by definition.

                                             If that doesn't
                                             make sense, try
Still, there's a strong trend of             reading:
thought that hierarchies are
traps: searching for the right                   RECURSIVE_DEFINITION
privileged node to put at the top
is a losing game.

   Distributed decision-making.
   Anarchic networks.
   Evolved structures.              CONTROL


        A way out of the Wasteland?


--------
[NEXT - CLOUDS]