functional programming & tail recursion?

[Dennis E. Hamilton]

I'm curious,

I can't imagine any language providing a very good result for

	def fib(n):
          assert n = int(n) and n = abs(n)
          if n in [0, 1]:
              return n
          return fib(n-1) + fib(n-2)

or any descriptive-language equivalent (Eiffel?).

Are you are thinking of descriptive languages that basically produce
computations by inferences of some kind?  I would want to know the order,
O(n), of the computation that actually occurs, I guess, in contrast to the
ease of expression and the appearance of simplicity.

I've seen functional-programming languages take the reverse approach:
applicative operators that construct iterations (in terms of the result
semantics), on the same principle as map-reduce sorts of operations.  The
implementation worked well (assuming that closures are inexpensive,
however).

Coming back to the claim that functional-programming is no good without
automatic tail-recursion reduction, I am hard pressed to see that as
*necessary*.  I can get it being recognition of a practice that has worked
in the absence of explicit iterative or recurrence forms.

Can you shed any light on that?

-- Dennis

PS: I understand that if I have a recurrence, it is easy to make a
tail-recursive equivalent.  Or a Prolog clause scheme.  I was looking at the
problem of having a recursive definition and doing the work to make it
tail-recursive equivalent.  I don't think one should begrudge an iterative
implementation (which is pretty immediate) as non-functional!  -- orcmid

------------------
Dennis E. Hamilton
InfoNuovo
mailto:infonuovo at email.com
tel. +1-206-779-9430 (gsm)
fax. +1-425-793-0283
http://www.infonuovo.com

-----Original Message-----
From: python-list-admin at python.org
[mailto:python-list-admin at python.org]On Behalf Of Tim Peters
Sent: Monday, February 28, 2000 22:18
To: python-list at python.org
Subject: RE: functional programming & tail recursion?

[ ... ]

> ...
> 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



--
http://www.python.org/mailman/listinfo/python-list