4/4     If you haven't seen it yet, this makes good reading:
        http://www.opencode.org/h2o    -brg
        \_ What is the G in Gnu's Not Unix? Every recursion has a base case
           right?
           \_ Not all recursion has a base case.  Try, e.g.,
                (define (foo) (foo))
              Or, more to the point,
                (define (gnu) (cons (gnu) '(is not unix)))
              Every example of recursion _that terminates_ has a base case,
              but recursion need not terminate.  See Hofstadter's _Godel,
              Escher, Bach_ for some discussion of infinite or non-terminating
              recursion, including in acronyms.  -- schoen
              \_ Every correct recursive function has a base case.  The
                 solution to Alan Turing's Halting problem is that if you
                 wrote the program correctly it should eventually terminate
                 IMHO.
                \_ How is that a solution to the halting problem?  The
                   halting problem is trying to figure out a way to
                   know if you wrote your program "correctly" (your
                   terminology)?  Your "solution" does not tell you
                   how you know if you wrote your program correctly.
                   \_ I thought the halting problem was if your program
                      would eventually finish.
                      \_ The Halting Problem is how you can _tell_.  It
                         happens to be equivalent to one form of program
                         correctness testing, but it's usually stated in
                         terms of the decision problem for programs' halting.
                 \_ What do you mean by a "correct recursive function"?