Tail recursion to while iteration in 2 easy steps
Steven D'Aprano
steve+comp.lang.python at pearwood.info
Wed Oct 2 15:13:57 EDT 2013
On Wed, 02 Oct 2013 10:04:49 -0400, random832 wrote:
> On Wed, Oct 2, 2013, at 9:32, Steven D'Aprano wrote:
>> Python is not as aggressively functional as (say) Haskell, but it is
>> surely an exaggeration to suggest that the failure to include tail call
>> optimization means that Python "rejects" functional programming styles.
>> You can still write you code in a functional style, it just won't be as
>> heavily optimized.
>
> IMO, tail call optimization is essential to writing in a functional
> style, since otherwise you end up with a stack overflow error on any
> input above a trivial size.
Hardly essential. Here's some functional code that doesn't rely on tail-
call optimization for efficiency:
result = map(some_function, some_iterator)
In Python 3 that even uses lazy evaluation, for free.
Or you can increase the amount of memory available in the stack. Another
alternative would be for the compiler to convert your recursive code into
iterative code. Well, that wouldn't work for Python.
Not all functional code is recursive, and not all recursive functional
code is tail-recursive. So while Python's lack of tail-call optimization
is a failure of Best Practice functional *implementation*, it doesn't
prevent you from writing in a functional *style*.
Ultimately, Python does not pretend to be a pure-functional language. If
you want Haskell, you know where to get it. Python steals a few good
ideas from functional programming, like comprehensions and lazy-evaluated
iterators, provides a few functional programming constructs like map,
reduce, and filter, and gives you first-class functions as values. You
can write code in a functional style in Python, but don't mistake that
for Python being a functional language.
--
Steven
More information about the Python-list
mailing list