```Subject: Re: Please help!!
From: Erik Naggum <erik@naggum.no>
Date: 1999/02/11
Newsgroups: comp.lang.lisp
Message-ID: <3127681433913250@naggum.no>

* cbarry@2xtreme.net (Christopher R. Barry)
| Freeing a programmer to not spend time and sacrifice maintainablity and
| readability converting a double recursive prototype into production code
| would be a nice win.

I hope I have not contributed to this confusion by trying to force people
to rethink this "recursive problem" thingie.  see, I don't _believe_ in
recursion in the moral sense of being _superior_ to iteration.  I think I
made the case that recursion is not as efficient as looping, but Barry is
quite right that the argument in favor of recursion doesn't seem to be
_total_ efficieny, just space efficiency.  however, to the people who
_believe_ in recursion, it should be valuable to understand that omitting
the prologue and epilogue of a machine-language function, as it were, is
not something you do lightly -- it adds significantly to the complexity
of the compiler.

some problems have not yet found solutions that can avoid space
requirements linear or worse in the length of the input.  I suspect those
are the ones people call "recursive problems", but when it is possible to
write algorithms that are sublinear in the length of the input, and smart
people continue to astound with more efficient algorithms like that all
the time, I'm not willing to buy the "intrinsically recursive" argument.

take Fibonacci, which is _defined_ recursively, but which can _easily_ be
implemented in constant memory and linear time.  so even if Fibonacci is
called a "recursive problem", the solution doesn't have to be.

in any case, if an algorithm has a space requirement linear in the length
of the input, you have a choice between real recursion and managing the
space requirements elsewhere.  sometimes, the stack space requirements of
function calls make it unpalatable to use actual recursion, and it's
easier to cons up the values on one or more lists.  however, this would
reduce the memory consumption with a constant number of bytes per call,
and you should be pretty hard pressed for memory before this begins to be
a serious impediment between "prototype" (another thing I don't _believe_
in) and production code.

| I'd like to know more about the specific technical hurdles involved in
| this type of thing, but this probably wasn't the right newsgroup to bring
| it up in.  And the answer is quite probably above my current level
| anyways, but it would give me a start.

discussions like these have raged in comp.compilers in the past, when I
had time to follow that group.  I learned a lot from following them, and,
incidentally, much more fundamental stuff than the compiler course at the
university, where the bondage with static typing was horribly stifling.
(just because it makes sense in some cases to declare or compute types in
the compiler doesn't mean it's smart to forget everything about types at
run-time, but for some people it seems that the entire goal of static
typing is to exclude type information at run-time, and I find that to be
curiously irrational.)   however, what has become clear is that a lot of
people have no clue what to do _without_ type declarations, and become
very insecure when they see Lisp programs without any explicit type
information at all, so I recommend to learn all there is about compilers
from the point of view that you _don't_ know the type of anything.  this
will improve your understanding greatly, as the explicit-typing crowd
tends to gloss over type problems in the simple cases, and then tackle
them inefficiently and clumsily in object systems and the like because
they have never had an incentive to make it super efficient.

sometimes, it helps to have been hurt by C, but I hope it's possible to
learn this stuff without the pain and suffering.  (a colleague was once
watching me working out how to deal with unclosed sockets in Allegro CL
under Linux, including comparing the symlinks in /proc/<pid>/fd/ to the
table in /proc/net/tcp by hand and isolating the stream object that used
it with a heap-walker -- this was before my auto-closing sockets -- and
he went "wow, I didn't know you were such an expert!".  I looked at him
wearily and said "`oooh, I didn't know you had been hurt that much' is a
lot more accurate.")

#:Erik
--
Y2K conversion simplified: Januark, Februark, March, April, Mak, June,
Julk, August, September, October, November, December.

```