functional programming & tail recursion?

[Tim Peters]

[Dennis E. Hamilton]
> I am a little puzzled by the discussion on tail recursion.  The seems to
> imply that tail recursion involves simply catching variations on the case
>
> 	def f(...):
>         stuff; ...;
>         return f(transformed ...)

Also tail-calls in general.  This comes primarily from the Scheme world,
which language has no iteration.  Scheme implementations are required (by
the Scheme std) to be "properly tail recursive", which is defined in such a
way that iteration can be written via recursion yet run in bounded space.
The same idea pops up in truly (which Scheme is not) functional languages
too, with somewhat more force, since a truly functional language has no
rebinding of names (try to write a useful loop wherein *nothing* can vary
<0.5 wink>).

> In my experience, most interesting recursive forms don't
> automatically take that structure.

Sure, but experienced Schemers can be very clever about bashing stuff into
that form.  In fact, they *have* to be to avoid the gross inefficiencies in
some of your recursive Fibonacci examples.  However, don't assume that's
hard!  Any loop you write can be easily expressed as a tail-recursive
function instead.  It's so easy that most Schemes even have a macro or two
that "look like loops" that automagically transfrom into recursive
functions.  Also don't assume that it's slow:  function calls in Scheme are
very much cheaper than in, e.g., Python.

> And when they do, one might as well go the rest of the way and implement
> the recurrence-iteration!

In Python, you bet.  It's not an option in functional languages, though.
But don't dismiss it out of hand -- there is great power hiding in the
approach.  If you're really curious, pick up Abelson & Sussman's "Structure
and Interpretation of Computer Programs", and use it to learn a little
Scheme and a lot of CompSci.

> ...
> The file also demonstrates why one indeed wants to replace recursive
> descents by recurrence iterations whenever possible.

In Python (and C, and C++, and Fortran, and Java, and Visual Basic, and
Perl, and JavaScript, and Tcl, and ...), yes.  In several other languages,
no.

you-can-ignore-it-in-python-for-decades-and-not-miss-a-thing-ly y'rs  - tim